链接：https://ac.nowcoder.com/acm/contest/329/B
来源：牛客网
输入文件第一行包含一个整数T，表示处女座要参加的比赛场数。
对于每一场比赛，第一行包含两个整数N,M，分别表示旅行中的站点数（其中宁波的编号为1，比赛地的编号为N）和线路数。
接下来M行，每一行包含5个整数u,v,c,cnz,jffzr，分别表示从u到v有一条单向的线路，这条线路的票价为c。处女座搭乘这条线路的时候，会得到cnz元（如果为负即为失去-cnz元）；经费负责人搭乘这条线路的时候，会得到jffzr元（如果为负即为失去-jffzr元）。
行程保证不会形成环，并保证一定能从宁波到达比赛地。
对于每一场比赛，如果经费负责人给出的经费绰绰有余，则先在一行输出"cnznb!!!"，并在下一行输出他可以余下的经费；如果处女座的经费不够用，则先在一行输出"rip!!!"，并在下一行输出他需要自费的金额；如果经费负责人给出的经费正好够处女座用，则输出一行"oof!!!"。（所有输出不含引号）
1≤M≤2?1051≤M≤2?105
1≤u,v≤N1≤u,v≤N
0≤c≤1090≤c≤109
?109≤cnz,jffzr≤109?109≤cnz,jffzr≤109
解题思路：题意比较明显是一个有向无环图即DAG图的最短路。由于含有负权值的边，所以肯定不能使用dijkstra，开始以为用spfa就可以了，没想到还是太天真了，真是学的太少了。特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案。考虑到 DAG 的特殊性，按照原图节点的拓扑顺序依次递推距离即可求解。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+7; const ll INF=1e18; struct Edge{ int to,next; ll cnz,jffzr; }edge[2*maxn]; int n,m,head[maxn],tot,Rudu[maxn]; ll dis[maxn]; ll min(ll a,ll b) { if(a>=b)return b; return a; } ll max(ll a,ll b) { if(a>=b)return a; return b; } void Add_Edge(int u,int v,ll c,ll d) { edge[tot].to=v; edge[tot].cnz=c; edge[tot].jffzr=d; edge[tot].next=head[u]; head[u]=tot++; } void Topsort(int id) { queue<int> que; while(que.size())que.pop(); for(int i=1;i<=n;i++){ dis[i]=INF; if(!Rudu[i])que.push(i); } dis[1]=0; while(que.size()) { int now=que.front(); que.pop(); for(int i=head[now];i!=-1;i=edge[i].next){ int v=edge[i].to; dis[v]=min(dis[v],dis[now]+(id==0?edge[i].cnz:edge[i].jffzr)); Rudu[v]--; if(Rudu[v]==0)que.push(v); } } } int main() { int T; scanf("%d",&T); while(T--) { tot=0; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++){ head[i]=-1; Rudu[i]=0; } for(int i=1;i<=m;i++) { int u,v; ll w,x,y; scanf("%d%d%lld%lld%lld",&u,&v,&w,&x,&y); Add_Edge(u,v,w-x,w-y); Rudu[v]++; } Topsort(0); ll ans1=max(0,dis[n]); Topsort(1); ll ans2=max(0,dis[n]); if(ans2-ans1>0){ puts("cnznb!!!"); cout<<ans2-ans1<<endl; } else if(ans2==ans1)puts("oof!!!"); else{ puts("rip!!!"); cout<<ans1-ans2<<endl; } } return 0; }
牛客寒假算法基础集训营3B 处女座的比赛资格（用拓扑排序解决DAG中的最短路）
原文：https://www.cnblogs.com/zjl192628928/p/10325885.html