Submission #75973079

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    const long long INF = 1e18;
    vector<vector<long long>> dist(M + 1, vector<long long>(M + 1, INF));
    for (int i = 1; i <= M; ++i) {
        dist[i][i] = 0;
    }

    for (int i = 0; i < K; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], (long long)w);
        dist[v][u] = min(dist[v][u], (long long)w);
    }

    // Floyd-Warshall all-pairs shortest path
    for (int k = 1; k <= M; ++k) {
        for (int i = 1; i <= M; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 1; j <= M; ++j) {
                if (dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    long long total = 0;
    for (int i = 0; i < N; ++i) {
        int s, t;
        cin >> s >> t;
        total += dist[s][t];
    }

    cout << total << '\n';
    return 0;
}

Submission Info

Judge Result