链接：https://ac.nowcoder.com/acm/contest/329/B
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
处女座想出去比赛，但是又不知道学校能不能给到足够的经费。然而处女座是大众粉丝，有着很好的人缘，于是他找了一个在学校管经费的地方勤工俭学偷来了一份报销标准。
由于处女座是万人迷，所以他在中间途径的每一条线路上都会发生一些故事，也许是粉丝给他发了一个200元的微信红包，也许是和他的迷妹一起吃饭花了500元。
而经费负责人也实地考察了每一条路线，在每一条路上，也许是天降红包雨，也许是地生劫匪。每一条路上都有属于自己的奇遇。
而经费负责人也只能根据他的故事决定这一路批下来多少经费。他会找出从宁波到比赛地的最小花费，并以此作为标准给处女座打比赛。而处女座也会选择对他来说最小花费的路线，来节省使用。
处女座想知道，最终的经费是否够用，如果够还会剩下来多少钱。如果不够，他自己要自费掏出多少钱。（当然处女座和经费管理人都具有旅途中无限信贷额度，所有收入支出会在旅行结束后一起结算。）
处女座想知道，最终的经费是否够用，如果够还会剩下来多少钱。如果不够，他自己要自费掏出多少钱。（当然处女座和经费管理人都具有旅途中无限信贷额度，所有收入支出会在旅行结束后一起结算。）
输入描述:
输入文件第一行包含一个整数T，表示处女座要参加的比赛场数。 对于每一场比赛，第一行包含两个整数N,M，分别表示旅行中的站点数（其中宁波的编号为1，比赛地的编号为N）和线路数。 接下来M行，每一行包含5个整数u,v,c,cnz,jffzr，分别表示从u到v有一条单向的线路，这条线路的票价为c。处女座搭乘这条线路的时候，会得到cnz元（如果为负即为失去-cnz元）；经费负责人搭乘这条线路的时候，会得到jffzr元（如果为负即为失去-jffzr元）。 行程保证不会形成环，并保证一定能从宁波到达比赛地。
输出描述:
对于每一场比赛，如果经费负责人给出的经费绰绰有余，则先在一行输出"cnznb!!!"，并在下一行输出他可以余下的经费；如果处女座的经费不够用，则先在一行输出"rip!!!"，并在下一行输出他需要自费的金额；如果经费负责人给出的经费正好够处女座用，则输出一行"oof!!!"。（所有输出不含引号）
示例1
输入
1
3 3
1 2 300 600 -600
2 3 100 -300 1
1 3 200 0 0
输出
cnznb!!!
100
说明
处女座先走第一条路再走第二条路到达，总花费100元，经费负责人走第三条路，花费200元，处女座经费剩余100元
备注:
T≤10T≤10
2≤N≤1052≤N≤105
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+;
const ll INF=1e18;
struct Edge{
int to,next; ll cnz,jffzr;
}edge[*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=;i<=n;i++){
dis[i]=INF;
if(!Rudu[i])que.push(i);
}
dis[]=;
while(que.size())
{
int now=que.front();
que.pop();
for(int i=head[now];i!=-;i=edge[i].next){
int v=edge[i].to;
dis[v]=min(dis[v],dis[now]+(id==?edge[i].cnz:edge[i].jffzr));
Rudu[v]--;
if(Rudu[v]==)que.push(v);
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
tot=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
head[i]=-;
Rudu[i]=;
}
for(int i=;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();
ll ans1=max(,dis[n]);
Topsort();
ll ans2=max(,dis[n]);
if(ans2-ans1>){
puts("cnznb!!!");
cout<<ans2-ans1<<endl;
}
else if(ans2==ans1)puts("oof!!!");
else{
puts("rip!!!");
cout<<ans1-ans2<<endl;
}
}
return ;
}