POJ--3259 Wormholes (SPFA判负环)

题目电波   3259 Wormholes

 

 

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stdio.h>
using namespace std;
#define maxn 100010
#define inf 0x3f3f3f3f
struct ac{
  int to,va;
  ac(){}
  ac(int a,int b){
    to=a,va=b;
  }
};
vector<ac>q[maxn];
int dis[maxn],vis[maxn];
bool fa[maxn];
int n,m,s;
void init(){
   for(int j=1;j<=maxn;j++) q[j].clear();
}
bool spfa(){
   memset(vis,0,sizeof(vis));
   memset(fa,0,sizeof(fa));
   memset(dis,inf,sizeof(dis));
   dis[1]=0;
   queue<int>pq;
   pq.push(1);
   while(!pq.empty()){
      int u=pq.front();
      pq.pop();
      fa[u]=0;
      for(int j=0;j<q[u].size();j++){
         int v=q[u][j].to;
         int va=q[u][j].va;
         if(dis[v]>dis[u]+va){
            dis[v]=dis[u]+va;
            if(!fa[v]){
               fa[v]=1;
               vis[v]++;
               pq.push(v);
               if(vis[v]>=n){
                 return 1;
               }
            }
         }
      }
   }
   return 0;
}
int main(){
   int t;
   cin>>t;
   while(t--){
    init();
     cin>>n>>m>>s;
     for(int j=0;j<m;j++){
        int u,v,va;
        scanf("%d%d%d",&u,&v,&va);
        q[u].push_back(ac(v,va));
        q[v].push_back(ac(u,va));
     }
     for(int j=0;j<s;j++){
        int u,v,va;
        scanf("%d%d%d",&u,&v,&va);
        q[u].push_back(ac(v,-va));
     }
     if(spfa()){
        cout<<"YES"<<endl;
     }else{
        cout<<"NO"<<endl;
     }
   }
}

 

全部评论

相关推荐

这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务