https://www.luogu.org/problem/P2446
变形最短路
定义dis表示最短路,w表示最早可以进入当前点的时间,w[x]=max{dis[x],max{w[pre]}},跑一遍Dijkstra。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=3005,M=70005; struct node { int h; ll d; }t; bool operator <(node a,node b) { return a.d>b.d; } priority_queue<node> q; int n,m,i,j,k,l,x,head[N],adj[M],nxt[M],len[M],Head[N],Adj[N*N],Nxt[N*N],d[N]; ll dis[N],w[N]; bool v[N]; inline void Read(int &x) { char c; while((c=getchar())<'0'||c>'9'); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=x*10+c-'0'; } int main() { scanf("%d%d",&n,&m); for(i=1;i<=m;++i) { scanf("%d%d%d",&j,&k,&x); adj[i]=k; nxt[i]=head[j]; head[j]=i; len[i]=x; } for(i=1;i<=n;++i) { scanf("%d",&j); d[i]=j; while(j--) { scanf("%d",&k); Adj[++l]=i; Nxt[l]=Head[k]; Head[k]=l; } } for(i=1;i<=n;++i) dis[i]=1ll<<60; w[1]=dis[1]=0; q.push((node){1,0}); while(!q.empty()) { t=q.top(); q.pop(); if(v[t.h]) continue; v[t.h]=true; w[t.h]=max(w[t.h],t.d); for(i=head[t.h];i;i=nxt[i]) if(w[t.h]+len[i]<dis[adj[i]]) { dis[adj[i]]=w[t.h]+len[i]; if(!d[adj[i]]) q.push((node){adj[i],dis[adj[i]]}); } for(i=Head[t.h];i;i=Nxt[i]) { --d[Adj[i]]; w[Adj[i]]=max(w[Adj[i]],w[t.h]); if(!d[Adj[i]]) q.push((node){Adj[i],dis[Adj[i]]}); } } printf("%lld",w[n]); return 0; }