牛客寒假算法基础集训营3 B. 处女座的比赛资格(DAG上拓扑排序)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客寒假算法基础集训营3 B. 处女座的比赛资格(DAG上拓扑排序)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1630字，纯文字阅读大概需要3分钟。

内容图文

 

题目链接：https://ac.nowcoder.com/acm/contest/329/B

       一道求最短路的题，但是存在负权，dij就写不了，然后考虑spfa的做法，因为题目中明确的说了有向无环图，所以根据DAG图的性质来说，spfa的做法不稳定，会超时，所以这里只能根据DAG图的特性来用拓扑排序来写，根据结点的入度来按顺序求最短路。

---

AC代码：

#include <bits/stdc++.h>
#define maxn 100005
#define maxm 200005
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Node{
  int to,next;
  ll w;
}Edge[maxm];
struct node{
  int u, v;
  ll w,c,j;
}a[maxm];
int head[maxn],num;
ll dist[maxn];
int dep[maxn];
int T,n,m;

void init(){
  num = 0;
  memset(head,-1,sizeof(head));
  memset(dist, inf, sizeof(dist));
  memset(dep, 0, sizeof(dep));
}

void add(int u,int v,ll w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

ll Topo(){
  queue<int> q;
  for(int i=1;i<=n;i++){
    if(dep[i] == 0) q.push(1);
  }
  dist[1] = 0;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int i=head[u];i!=-1;i=Edge[i].next){
      int v = Edge[i].to;
      if(dist[v] > dist[u] + Edge[i].w){
        dist[v] = dist[u] + Edge[i].w;
      }
      if(-- dep[v] == 0){
        q.push(v);
      }
    }
  }
  return dist[n] >= 0 ? dist[n] : 0;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    init();
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
      scanf("%d%d%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w,&a[i].c,&a[i].j);
      add(a[i].u, a[i].v, a[i].w - a[i].c);
      dep[a[i].v] ++;
    }
    ll ans1 = Topo();
    init();
    for(int i=0;i<m;i++){
      add(a[i].u, a[i].v, a[i].w - a[i].j);
      dep[a[i].v] ++;
    }
    ll ans2 = Topo();
    // cout<<ans1<<"  "<<ans2<<endl;
    if(ans1 == ans2) puts("oof!!!");
    else if(ans1 < ans2){
      puts("cnznb!!!");
      printf("%lld\n", ans2 - ans1);
    }
    else{
      puts("rip!!!");
      printf("%lld\n", ans1 - ans2);
    }
  }
  return 0;
}

 

内容总结

以上是互联网集市为您收集整理的牛客寒假算法基础集训营3 B. 处女座的比赛资格(DAG上拓扑排序)全部内容，希望文章能够帮你解决牛客寒假算法基础集训营3 B. 处女座的比赛资格(DAG上拓扑排序)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---