【題解】TIOJ 1096 . E.漢米頓的麻煩

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1096
【解題想法】Floyd-Warshall algorithm 計算最短路徑

#include <iostream>
#include <cstring>
using namespace std;

long long a[100][100], num = 0x3F3F3F3F3F3F3F3F, tmp;

int main() {
    long long n, mn;
    while (cin >> n){
        if (n == 0) break;
        memset(a, 0x3F, sizeof(a));
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cin >> tmp;
                if (tmp != 0) a[i][j] = tmp;
            }
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < n; k++){
                    if (a[j][k] > a[j][i] + a[i][k]){
                        a[j][k] = a[j][i] + a[i][k];
                    }
                }
            }
        }
        mn = num;
        for (int i = 0; i < n; i++){
            mn = min(mn, a[i][i]);
        }
        if (mn == num) cout << -1 << "\n";
        else cout << mn << "\n";
    }
}
分享本文 Share with friends