6

POJ 3259

• 题意：能否通过负边回到过去，意思是求是否存在负权环.

• 开一个cnt[]记录每一个点访问的次数,如果存在负权环那么一定能一直松弛

   #include <iostream>
  #include <queue>
  #include <vector>
  #include <string.h>
  
  using namespace std;
  const int maxn = 505;
  
  vector<pair<int,int> > e[maxn];
  bool vis[maxn];
  int dist[maxn];
  int n,m,negative;
  int cnt[maxn];
  
  bool bellmanford() {
  	queue<int> que;
  	memset(dist,0x3f,sizeof dist);
  	memset(cnt,0,sizeof cnt);
  	memset(vis,0,sizeof vis); 
  	vis[1] = 1; dist[1] = 0;
  
  	que.push(1);
  
  	while (!que.empty()) {
  		int cur = que.front(); que.pop();
  		vis[cur] = 0;
  		for (int i=0; i<e[cur].size(); i++) {
  			int to = e[cur][i].first;
  			int div = e[cur][i].second;
  			if (dist[to] > dist[cur] + div) {
  				dist[to] = dist[cur] + div;
  				if (!vis[to]) {
  					vis[to] = 1;
  					que.push(to);
  				}
  				if (++cnt[to] > n) return 1;
  			}
  		}
  	}
  	return false;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	int times;
  	cin >> times;
  	while (times--) {
  		for (int i=1; i<=n; i++) e[i].clear();
  		scanf("%d%d%d",&n,&m,&negative);
  		int u,v,w;
  		for (int i=1; i<=m; i++) {
  			scanf("%d%d%d",&u,&v,&w);
  			e[u].push_back( make_pair(v,w) );
  			e[v].push_back( make_pair(u,w) );
  		}
  		for (int i=1; i<=negative; i++) {
  			scanf("%d%d%d",&u,&v,&w);
  			e[u].push_back( make_pair(v,-w) );
  		}
  
  		if (bellmanford()) cout << "YES\n";
  		else cout << "NO\n";
  		for (int i=1; i<=n; i++) e[i].clear(); 
  	}
  	return 0;
  }