kuangbin专题专题四 Wormholes POJ - 3259 - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://vjudge.net/problem/POJ-3259

思路：求有无负环，起点随意选就可以，因为目的只是找出有没有负环，有了负环就可以让时间一直回退，那么一定能回到当初，这里我选择从1号点开始。

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <cstdio>

 #include <string>

 #include <vector>

 using namespace std;

 typedef long long LL;

 #define inf (1LL << 30) - 1

 #define rep(i,j,k) for(int i = (j); i <= (k); i++)

 #define rep__(i,j,k) for(int i = (j); i < (k); i++)

 #define per(i,j,k) for(int i = (j); i >= (k); i--)

 #define per__(i,j,k) for(int i = (j); i > (k); i--)

 const int N = ;

 int dis[N];

 int n,m,t;

 int u,v,w;

 struct node{

     int u,v,w;

 };

 vector<node> E;

 void init(){

     memset(dis,inf,sizeof(dis));

     E.clear();

 }

 void input(){

     rep(i,,m){

         cin >> u >> v >> w;

         E.push_back(node{u,v,w});

         E.push_back(node{v,u,w});

     }

     rep(i,,t){

         cin >> u >> v >> w;

         E.push_back(node{u,v,-w});

     }

 }

 bool bellman_ford(){

     dis[] = ;

     bool flag = true;

     rep(i,,n){

         flag = false;//判断一层循环中有没有出现可以更新的点

         for(int o = ; o < E.size(); o++){

             if(dis[E[o].v] > dis[E[o].u] + E[o].w)

                 dis[E[o].v] = dis[E[o].u] + E[o].w;

             flag = true;//还有可以更新的点

         }

         if(!flag) break;//不存在可以更新的点了，直接退出

     }

     //判断有无负环出现，即时间能不能减少

     for(int o = ; o < E.size(); o++){

         if(dis[E[o].v] > dis[E[o].u] + E[o].w) return true;

     }

     return false;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();

     int T;

     cin >> T;

     while (T--){

         cin >> n >> m >> t;

         init();

         input();

         if(bellman_ford()) cout << "YES" << endl;

         else cout << "NO" << endl;

     }

     getchar();getchar();

     return ;

 }