http://acm.pku.edu.cn/JudgeOnline/problem?id=3169参考 http://www.cppblog.com/Darren/archive/2009/07/20/90649.html写的Bellman_Ford
  code
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=20000+10;
const int maxd=10000+10;
const int inf=2000000;
struct Edge
{
int u,v,w;
Edge(int u=0,int v=0,int w=0):
u(u),v(v),w(w)
{}
};
Edge edge[maxn];
int s=0;
int n,ml,md;
int dist[maxd];
int Bellman_Ford()
{
bool flag;
for(int i=1;i<=n;i++)
dist[i]=inf;
dist[1]=0;
for(int i=1;i<=n;i++) //松弛n遍。如果没有负权回路，则最多只要松弛n-1遍即可。如果第n遍仍可松弛，说明有负权回路
{
flag=0;
for(int j=0;j<s;j++)
{
int u=edge[j].u,v=edge[j].v,w=edge[j].w;
if(dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;
flag=1;
}
}
if(!flag) break; //说明已经没有边可以松弛了
}
if(flag) return -1; //说明第n遍循环中，仍有边可以松弛，说明有负权回路
else if(dist[n]==inf) return -2;
else return dist[n];
}
int main()
{
int u,v,w;
scanf("%d%d%d",&n,&ml,&md);
while(ml--)
{
scanf("%d%d%d",&u,&v,&w);
edge[s++]=Edge(u,v,w);
}
while(md--)
{
scanf("%d%d%d",&u,&v,&w);
edge[s++]=Edge(v,u,-w);
}
printf("%d\n",Bellman_Ford());
}
|