louisfghbvc的部落格

題目連結:   12319.pdf (nsysu.edu.tw)

題目大意:  一張無向圖，一張有向圖，計算所有點最短路。每個有向圖的最短路不能超過無向圖的A倍+B

思路:  Floyd Warshall。如果是CPE的題目要多算原本的最大的最短路徑。Uva就只需判斷有向圖有沒有超過A倍+B。

難在讀題。

代碼:  

#include <bits/stdc++.h>
using namespace std;

int g1[105][105];
int g2[105][105];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n, n){
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                g1[i][j] = g2[i][j] = 1e5;

        cin.ignore();

        string str;
        for(int i = 1; i <= n; ++i){
            getline(cin, str);
            stringstream ss(str);
            ss >> i;
            int v;
            while(ss >> v){
                g1[i][v] = 1;
            }
        }

        for(int i = 1; i <= n; ++i){
            getline(cin, str);
            stringstream ss(str);
            ss >> i;
            int v;
            while(ss >> v){
                g2[i][v] = 1;
            }
        }

        int a, b;
        cin >> a >> b;

        for(int k = 1; k <= n; ++k){
            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j){
                    g1[i][j] = min(g1[i][j], g1[i][k] + g1[k][j]);
                    g2[i][j] = min(g2[i][j], g2[i][k] + g2[k][j]);
                }
            }
        }

        bool g = 0;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(i == j) continue;
                if(g2[i][j] > g1[i][j] * a + b) g = 1;
            }
        }

        cout << (g ? "No" : "Yes") << "\n";
    }
}