题目链接

Convenient Location Aizu - 0189

思路

$$ Floyd-Warshall算法模板题,for for for $$

时间复杂度

$$ O(N^3) $$

代码

#include <cstdio>
#include <vector>

using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

class Floyd {
public:
    typedef long long T;

    vector<vector<T> > dist;
    int n;

    void init(int _n) {
        n = _n;
        vector<T> temp(n + 5);
        dist.resize(n + 5, temp);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dist[i][j] = INF;
                if (i == j) {
                    dist[i][j] = 0;
                }
            }
        }
    }

    void add_edge(int u, int v, T w) {
        dist[u][v] = min(dist[u][v], w);
    }

    void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    void gao() {
        for (int k = 0; k <= n; k++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0;j <= n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

};



int main() {
    Floyd floyd;
    int n;
    while (scanf("%d", &n), n) {
        floyd.init(10);
        while (n--) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);// don't forget &
            floyd.add_edges(u, v, w);
        }
        floyd.gao();
        int id = 0;
        long long ans = INF;
        for (int i = 0; i < 10; i++) {
            long long cur = 0;
            for (int j = 0; j < 10; j++) {
                if (floyd.dist[i][j] != INF) {
                    cur += floyd.dist[i][j];
                }
            }
            if (cur != 0 && cur < ans) {
                id = i;
                ans = cur;
            }
        }
        printf("%d %lld\n", id, ans);
    }

    return 0;
}