首页 / 软件开发 / 数据结构与算法 / POJ 1860 Currency Exchange：最短路 Bellman-Ford

POJ 1860 Currency Exchange：最短路 Bellman-Ford2015-02-25Currency Exchange：http://poj.org/problem？id=1860

大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。

思路：Bellman_Ford，因为要求最长路，所以松弛条件改一下就好了。

Tips：

3              2                  1                20.0
货币的数量   兑换点的数量     主人公拥有的货币量    主人公拥有货币的价值1 2 1.00 1.00 1.00 1.00
//货币1与货币2交换时，1与2的汇率是1.00,1换2的手续费是1.00,2与1的汇率是1.00,2换1的手续费是1.00。2 3 1.10 1.00 1.10 1.00
//货币1与货币2交换时，1与2的汇率是1.10,1换2的手续费是1.00,2与1的汇率是1.10,2换1的手续费是1.00。

#include <stdio.h>#include <iostream>#include <map>#include <stack>#include <string.h>#define INF 0x3f3f3f3fusing namespace std;int n, m, s;double v;double dis[110];int t;struct node{int x, y;double r, c;} Map[210];bool Bellman_Ford（）{memset（dis, 0, sizeof（dis））;dis[s] = v;for（int i = 1; i <= n-1; i++）{bool flag = false;for（int j = 0; j < t; j++）{if（dis[Map[j].y] < （dis[Map[j].x]-Map[j].c）*Map[j].r）{dis[Map[j].y] = （dis[Map[j].x]-Map[j].c）*Map[j].r;flag = true;}}if（！flag）{break;}}for（int i = 0; i < t; i++）{if（dis[Map[i].y] < （dis[Map[i].x]-Map[i].c）*Map[i].r）{return true;}}return false;}void Solve（）{int a, b;double Rab, Rba, Cab, Cba;while（~scanf（"%d%d%d%lf", &n, &m, &s, &v））{t = 0;for（int i = 0; i < m; i++）{scanf（"%d%d%lf%lf%lf%lf", &a, &b, &Rab, &Cab, &Rba, &Cba）;Map[t].x = a;Map[t].y = b;Map[t].r = Rab;Map[t++].c = Cab;Map[t].x = b;Map[t].y = a;Map[t].r = Rba;Map[t++].c = Cba;}if（Bellman_Ford（））{printf（"YES
"）;}else{printf（"NO
"）;}}}int main（）{Solve（）;return 0;}

From：cnblogs GLsilence