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;i v)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；不知道为什么。
