UVA104Arbitrage（floyd最短路）

本文主要是介绍UVA104Arbitrage（floyd最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA104Arbitrage

题目大意：
给你两两国家之间的汇率，要求你从任何一个国家出发，身上带着1(单位不明），然后回到这个国家时，身上的钱能够> 1.01.并且如果这样的路径有多条的话，希望的到的是最短的路径，并且还有要求你输出这个最短的路径。

解题思路：
利用floyd可以求出旅游任何两个国家的可以得到的最大的金钱，可是无法获得最短的路径，最短路径的意思是中转的国家数尽量少。因此需要再加上一维来标记国家i到j，中间经过了p个中间的国家到达（包括i）。那么G【i】【j】【p】 = max （G【i】【j】【p】， G【i】【k】【p - 1】 * G【k】【j】【1】）;并且用path【i】【j】【p】记录中转的城市。

代码：


#include <cstdio>
#include <cstring>const int maxn = 30;int n;
int path[maxn][maxn][maxn];
double table[maxn][maxn][maxn];void init () {memset(table, 0, sizeof(table));memset(path, -1, sizeof(path));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++) {if (i == j) {table[i][j][1] = 0;}else {scanf ("%lf", &table[i][j][1]);}}}int floyd (int &p) {for (p = 1; p < n; p++)for (int k = 0; k < n; k++)for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {if (table[i][k][p] * table[k][j][1] > table[i][j][p + 1]) {table[i][j][p + 1] = table[i][k][p] * table[k][j][1];path[i][j][p + 1] = k;}if (i == j && table[i][j][p + 1] > 1.01)    return i;}return -1;
}void print_path(int start, int end, int p) {int next = path[start][end][p];if (next == -1)return;print_path(start, next, p - 1);printf("%d ", next + 1);print_path(next, end, 1);
}int main () {while (scanf ("%d", &n) != EOF) {init();int p;int start = floyd(p);
//      printf ("%d\n", start);if (start == -1)printf ("no arbitrage sequence exists\n");else {printf ("%d ", start + 1);print_path(start, start, p + 1);printf ("%d\n", start + 1);}}return 0;
}