题目地址：http://poj.org/problem?id=3259
裸的算法
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int INF=(1<<30); struct Edge{ int from,to,weight; Edge(int f,int t,int w):from(f),to(t),weight(w){} }; vector<Edge> edges; int dist[1000+5]; bool Bellman_ford(int s,int n) { for(int i=0;i<n;i++) dist[i]=INF; dist[s]=0; for(int k=1;k<n;k++) //从u~v点经过k条边 for(int i=0;i<edges.size();i++) { int u=edges[i].from; int v=edges[i].to; int w=edges[i].weight; dist[v]=min(dist[v],dist[u]+w); } for(int i=0;i<edges.size();i++){ int u=edges[i].from; int v=edges[i].to; int w=edges[i].weight; if(dist[v]>dist[u]+w) return true; } return false; } int main() { int T; cin>>T; while(T--) { int N,M,W; cin>>N>>M>>W; int u,v,w; edges.clear(); while(M--) { cin>>u>>v>>w; edges.push_back(Edge(u,v,w)); edges.push_back(Edge(v,u,w)); } while(W--) { cin>>u>>v>>w; edges.push_back(Edge(u,v,-w)); } cout<<(Bellman_ford(1,N)?"YES":"NO")<<endl; } return 0; }