本文主要是介绍牛客寒假算法基础集训营3-B-处女座的比赛资格（DAG上的最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://ac.nowcoder.com/acm/contest/329/B
思路：首先这题可以用最短路来搞，只不过题目说行程不会形成环，也就是DAG图（有向无环图），spfa会超时，有负权值的边也不能用dijkstra，既然是DAG图那起点的入度必为0，我们可以用拓扑排序，去边的时候更新花费，然后判断两种花费情况即可。
AC代码1：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
#define inf 0x3f3f3f3f
#define pii pair<int, int>
int n, m, s, t;
int d[maxn], vis[maxn], dep[maxn];
struct node{int u, to, w, cnz,jffzr;
}a[maxn];
vector <pii> E[maxn];
void init()
{for(int i = 0; i <= n; i++) E[i].clear();memset(d,0x3f,sizeof(d));memset(vis,0,sizeof(vis));memset(dep, 0, sizeof(dep));
}
int Topo()
{queue <int> Q;for(int i = 1; i <= n; i++)if(dep[i] == 0) Q.push(i);d[1] = 0;while(!Q.empty()){int now = Q.front();Q.pop();for(int j = 0; j < E[now].size(); j++){int v = E[now][j].first;if(d[v] > d[now]+E[now][j].second)d[v] = d[now]+E[now][j].second;if(--dep[v] == 0) Q.push(v);}}return max(0, d[n]);
}
int main()
{int t; scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();for(int i = 0; i < m; i++){scanf("%d%d%d%d%d",&a[i].u,&a[i].to,&a[i].w,&a[i].cnz,&a[i].jffzr);E[a[i].u].push_back({a[i].to,a[i].w-a[i].cnz});dep[a[i].to]++;}int ans1 = Topo();init();for(int i = 0; i < m; i++){E[a[i].u].push_back({a[i].to,a[i].w-a[i].jffzr});dep[a[i].to]++;}int ans2 = Topo();if(ans2 == ans1) printf("oof!!!\n");else if(ans2 > ans1) printf("cnznb!!!\n%d\n",ans2-ans1);else printf("rip!!!\n%d\n",ans1-ans2);}return 0;
}
AC代码2：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int maxm = 2e5+10;
struct DAG
{int n,tot;int head[maxn];int du[maxn]; //入度long long dis[maxn];struct Node{int to,next;long long d;}edge[maxm];void init(int nn){n = nn;memset(head,0,sizeof(head));memset(du,0,sizeof(du));memset(dis,0x3f,sizeof(dis));tot = 0;}void addedge(int u,int v,long long dd){edge[++tot].to = v;edge[tot].d = dd;edge[tot].next = head[u];head[u] = tot;du[v]++;}long long solve(){queue <int> Q;dis[1] = 0;for(int i = 1; i <= n; i++) if(du[i]==0) Q.push(i);while(!Q.empty()){int now = Q.front();Q.pop();for(int i = head[now]; i; i = edge[i].next){int to = edge[i].to;long long d = edge[i].d;dis[to] = min(dis[to],dis[now]+d);if(--du[to] == 0) Q.push(to);} }return max(0ll, dis[n]);}
}A,B;
int main()
{int T,m,n,u,v;long long c,d,e;cin >> T;while(T--){scanf("%d%d",&n,&m);A.init(n); B.init(n);while(m--){scanf("%d%d%lld%lld%lld",&u,&v,&c,&d,&e);A.addedge(u, v, c - d);B.addedge(u, v, c - e);}long long ans1 = A.solve();long long ans2 = B.solve();if(ans2 == ans1) printf("oof!!!\n");else if(ans2 > ans1) printf("cnznb!!!\n%lld\n",ans2 - ans1);else printf("rip!!!\n%lld\n",ans1 - ans2);}return 0;
}
这篇关于牛客寒假算法基础集训营3-B-处女座的比赛资格（DAG上的最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
