题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1922
带限制最短路。
每个点真正的dis是max(dis[i],dis[v]),v是其保护点。
可以把题目中的保护转化为每个点的贡献。
每次扫一边连出的边做最短路把rd为0的点加入队列。
再扫一遍自己的贡献，更新它们的d2，并让rd--，其中rd为0的点加入队列。
（注意一下优先队列是大根堆。
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 3005 using namespace std; struct data{int x,y; }; struct edge{int obj,pre,c; }e[70050]; int a[maxn][maxn],d1[maxn],d2[maxn],head[maxn],vis[maxn],rd[maxn],l[maxn]; int n,m,tot,mx; int read(){int x=0,f=1; char ch=getchar();while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}return x*f; } void insert(int x,int y,int z){e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot; e[tot].c=z; } bool operator <(data a,data b){return a.y>b.y;//return a.x<b.x; } void dij(){priority_queue<data> q; q.push((data){1,0});clr(d1,127/3); d1[1]=0;while (!q.empty()){int u=q.top().x; q.pop();if (vis[u]) continue; vis[u]=1;int mx=max(d1[u],d2[u]);for (int j=head[u];j;j=e[j].pre){int v=e[j].obj;if (mx+e[j].c<d1[v]) {d1[v]=mx+e[j].c;if (!rd[v]) q.push((data){v,max(d1[v],d2[v])});}}rep(i,1,l[u]){int v=a[u][i];rd[v]--; d2[v]=max(d2[v],mx);if (!rd[v]) q.push((data){v,max(d1[v],d2[v])});}} } int main(){n=read(); m=read();rep(i,1,m){int x=read(),y=read(),z=read();insert(x,y,z);}rep(i,1,n){rd[i]=read();rep(j,1,rd[i]){int x=read();a[x][++l[x]]=i;}}dij();printf("%d\n",max(d1[n],d2[n]));return 0; }
