这题是一道有限制的最短路题。 如果没有限制，刷一次最短路就行了，但是是有限制的，即走一个点之前必须要先走另外几个点。那么我们应该怎样处理呢。 这里其实有一个贪心的想法，刷Dijkstra。（这个算法本身就是贪心）对于当前的每一个点，求出其”需要多久才能走到”以及”多久才能销毁它的所有限制条件”这两个量，求一个时间的max就是走到这个点的真实时间。接下去用这个真实时间去修正其它的点，直到刷到n就是最终的答案了。 代码如下（dijkstra+堆）：
#include<cstdio> #include<string> #include<cstring> #include<queue> using namespace std; const int maxn=3005,maxm=1000005; int n,m,tot,lnk[2][maxn],sum[maxn],w[maxm],son[maxm],nxt[maxm],dis[2][maxn]; bool vis[maxn]; struct dyt{ int x,id; bool operator <(const dyt b) const{return x>b.x;} }; priority_queue<dyt> hep; inline int read(){ int x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x; } void add(int x,int y,int z,int pd){ son[++tot]=y,w[tot]=z,nxt[tot]=lnk[pd][x],lnk[pd][x]=tot; } dyt makep(int x,int y){dyt a; a.id=x,a.x=y; return a;} int getmin(int x) {return max(dis[0][x],dis[1][x]);} int dij(){ memset(dis[0],63,sizeof(dis[0])); dis[0][1]=dis[1][1]=0,hep.push(makep(1,getmin(1))); while (hep.size()>0) { dyt a=hep.top(); while (vis[a.id]) {hep.pop(); a=hep.top();} if (a.id==n) return a.x; vis[a.id]=1; hep.pop(); for (int j=lnk[0][a.id];j;j=nxt[j]){ dis[0][son[j]]=min(dis[0][son[j]],a.x+w[j]); if (!sum[son[j]]) hep.push(makep(son[j],getmin(son[j]))); } for (int j=lnk[1][a.id];j;j=nxt[j]){ dis[1][son[j]]=max(dis[1][son[j]],a.x); sum[son[j]]--; if (!sum[son[j]]) hep.push(makep(son[j],getmin(son[j]))); } } } int main(){ n=read(),m=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(x,y,z,0); } for (int i=1;i<=n;i++) { sum[i]=read(); for (int j=1;j<=sum[i];j++) {int x=read(); add(x,i,0,1);} } printf("%d\n",dij()); return 0; }