程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA104Arbitrage(floyd最短路)

UVA104Arbitrage(floyd最短路)

編輯:C++入門知識

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved