题目地址：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;
}