Bellman-Ford 算法描述：

1.创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，

初始均为 Infinite，源顶点距离为 0；

2.计算最短路径，执行 V - 1 次遍历；对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点v 的距离值 d；

3.检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

 

题目大意：

很久以前看见的题目没做，因为是英文不想看，今天还是做了：

题意：一个城市里有很多货币兑换点，每个兑换点可以兑换不同的货币，比如说a兑换b有一个兑换率r,还有一个手续费c,那么有价值v的a货币兑换成b货币就有（a-c）*r。现在输入n,m,s,v;表示有n种货币，m个兑换点，刚开始拥有的货币种类编号为s,价值为v。每个兑换点输入a,b,Rab,Cab,Rba,Cba,这个兑换点用a兑换b和b兑换a的兑换率和手续费。

 

#include
#include
#include
#define N 1500
#define inf 99999
using namespace std;
double r[N][N];//兑换率 
double c[N][N];//手续费 
double w[N];//原钱数换成i号钱之后的单位数 
int is[N][N]={0};//表示是否能换 
void input(int n,int m,int s,double v)
{
	
	
	for(int i=0;i>a>>b;
		cin>>r[a][b]>>c[a][b]>>r[b][a]>>c[b][a];
		is[a][b]=1;//a到b能换 
		is[b][a]=1;
		
	}
}
void solve(int n,int m,int s,double v)//n种货币，m个兑换点，货币种类编号为s,价值为v。
{
	/*for(int i=1;i<=n;i++)//自己和自己能换 
	{
		is[i][i]=1;
	}*/
	/*for(int i=1;i<=n;i++)
	{
		if(is[s][i]==1)
		{
			w[i]=(v-c[s][i])*r[s][i];
		}
	}*/
	for(int i=1;iv)cout<<"YES"<>n>>m>>s>>v;
	
		for(int i=0;i<=n;i++)//距离初始化成
		{
			w[i]=-1000000;
		}
		w[s]=v;
		input(n,m,s,v);
		solve(n,m,s,v);
		output(n,m,s,v);
		
	
	return 0;
}

显然（虽然这个词不太好委屈）：有正权环则yes，负权环或者无环no！！！！

 

前几次wa了：关于为什么一定要重新循环一次看看能不能再松弛，而不能看循环之后看w[s]是不是大于v，是因为，有可能s并不在环里面，而且循环次数不一定足够能更新到s。

 

另注：cin>>a>>b>>r[a][b]>>c[a][b]>>r[b][a]>>c[b][a];会runtime error；不知道为什么。