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
#include
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;
}