传送门：poj3259 Wormholes
1.Bellman-ford
//poj3259
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=510;
int F,M,N,W;struct Edge{int s,e,w;Edge(int s_,int e_,int w_):s(s_),e(e_),w(w_){}Edge(){}
};vector<Edge> edges; //所有边
int dist[maxn];bool Bellman_ford(int v){memset(dist,INF,sizeof(dist));dist[v]=0;for(int k=1;k<N;k++){for(int i=0;i<edges.size();i++){int s=edges[i].s;int e=edges[i].e;if(dist[s]+edges[i].w<dist[e]) dist[e]=dist[s]+edges[i].w;}}for(int i=0;i<edges.size();i++){int s=edges[i].s;int e=edges[i].e;if(dist[s]+edges[i].w<dist[e]) return true;}return false;
} int main(){cin>>F;while(F--){edges.clear();cin>>N>>M>>W;for(int i=0;i<M;i++){int s,e,t;cin>>s>>e>>t;edges.push_back(Edge(s,e,t));edges.push_back(Edge(e,s,t));}for(int i=0;i<W;i++){int s,e,t;cin>>s>>e>>t;edges.push_back(Edge(s,e,-t));}if(Bellman_ford(1)) puts("YES"); //从1可达所有点 else puts("NO");}return 0;
}
2.SPFA
//poj3259
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=510;
int F,M,N,W;struct Edge{int e,w;Edge(int e_,int w_):e(e_),w(w_){}Edge(){}
};vector<Edge> G[maxn]; //整个有向图
int updateTimes[maxn]; //最短路的更新次数
int dist[maxn]; //dist[i]是源到i的目前最短路长度 bool SPFA(int v){memset(dist,INF,sizeof(dist));dist[v]=0;queue<int> que;que.push(v);memset(updateTimes,0,sizeof(updateTimes));while(!que.empty()){int s=que.front();que.pop();for(int i=0;i<G[s].size();i++){int e=G[s][i].e;if(dist[e]>dist[s]+G[s][i].w){dist[e]=dist[s]+G[s][i].w;que.push(e);updateTimes[e]++;if(updateTimes[e]>=N) return true;}}}return false;
} int main(){cin>>F;while(F--){cin>>N>>M>>W;for(int i=1;i<maxn;i++)G[i].clear();for(int i=0;i<M;i++){int s,e,t;cin>>s>>e>>t;G[s].push_back(Edge(e,t));G[e].push_back(Edge(s,t));}for(int i=0;i<W;i++){int s,e,t;cin>>s>>e>>t;G[s].push_back(Edge(e,-t));}if(SPFA(1)) puts("YES"); else puts("NO");}return 0;
}