这道题目是属于POJ训练计划里面的求最短路径里面的。
主要运用了Bellman-Ford算法。
算法的主要功能：求可能存在负值回路的图中，是否存在负值回路。
其算法的主要执行过程是：
========================================
for(每一个节点）
Distanz(v) := 无穷大；Predecessor(v) := null //Distanz(v)为v的权值
Distanz(s) := 0，Predecessor(s):= null; //s为起点
for(每一个节点）
for(每一个路径)
if Distanz(u) + weight(u,v) < Distanz(v)
{
Distanz(v) := Distanz(u) + weight(u,v)
Predecessor(v) := u;
}
for 每一条路径 （u，v）属于 E
if Distanz(u) + weight(u,v) < Distanz(v)
then
中止程序并且返回 “找到负循环”
返回
==============================================
这道题目的代码：
#include<stdio.h>
struct list
{double r;double c;
}map[300][300];
int kind,num,kind_have;
double money_have;
int bf()
{int i,j,k;double d[300];for(i=0;i<=kind;i++){d[i]=0;//把每一个节点的权值归零}d[kind_have]=money_have;for(k=1;k<=kind;k++)//对于每一个节点{for(j=1;j<=kind;j++)//这个for和下一个for一起构成了所有的路径{for(i=1;i<=kind;i++){if(d[i]<(d[j]-map[j][i].c)*map[j][i].r){d[i]=(d[j]-map[j][i].c)*map[j][i].r;}}}} for(j=1;j<=kind;j++){for(i=1;i<=kind;i++){if(d[i]<(d[j]-map[j][i].c)*map[j][i].r){return 1;}}}return 0;
}
int main()
{int a,i,b,j;scanf("%d%d%d%lf",&kind,&num,&kind_have,&money_have);for(i=0;i<300;i++){for(j=0;j<300;j++){map[i][j].r=0;}}for(i=0;i<num;i++){scanf("%d%d",&a,&b);scanf("%lf%lf",&map[a][b].r,&map[a][b].c);scanf("%lf%lf",&map[b][a].r,&map[b][a].c);}if(bf()==1)printf("YES\n");elseprintf("NO\n");return 0;
}