vjudge题目链接

昨天做这题交了10遍都是WA,不知道哪里的问题,今天重写就过了,还是重写大法好啊。

cpp代码:

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

const int maxn = 1024;
int n, d[maxn][maxn], b[maxn], path[maxn][maxn];

void Flody() {
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            path[i][j] = j;
    for(int k = 1; k <= n; ++k) {
        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j <= n; ++j) {
                int t = d[i][k] +  d[k][j] + b[k];
                if(t < d[i][j]) {
                    d[i][j] = t;
                    path[i][j] = path[i][k];
                }
                else if(t == d[i][j] && path[i][j] > path[i][k]) {
                    path[i][j] = path[i][k];
                }
            }
        }
    }
}

int main()
{
    while(cin >> n, n) {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                cin >> d[i][j];
                if(d[i][j] == -1)
                    d[i][j] = 99999999;
            }
        }
        for(int i = 1; i <= n; ++i)
            cin >> b[i];
        Flody();
        int u, v;
        while(cin >> u >> v) {
            if(u == -1 && v == -1) break;
            int cost = d[u][v];
            printf("From %d to %d :\n", u, v);
            printf("Path: %d", u);
            while(u != v) {
                printf("-->%d", path[u][v]);
                u = path[u][v];
            }
            printf("\nTotal cost : %d\n\n", cost);
        }
    }
    return 0;
}

欢迎留言