Submission #1789983

---

Source Code Expand

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

#define INF (1<<29)

int main() {
    int n, m, r;
    cin >> n >> m >> r;
    vector<int> R(r);
    for (int i = 0; i < r; i++) {
        int a; cin >> a;
        R[i] = a - 1;
    }
    int M[209][209];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            /*
            if (i == j) {
                M[i][j] = 0;
            } else {
            */
            if (i != j) {
                M[i][j] = INF;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        if (M[a][b] > c) {
            M[a][b] = M[b][a] = c;
        }
    }

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

    sort(R.begin(), R.end());

    long long ans = 1e9;
    do {
        long long sum = 0;
        for (int i = 0; i < (r-1); i++) {
            sum += M[ R[i] ][ R[i+1] ];
        }
        ans = min(sum ,ans);
    } while ( next_permutation(R.begin(), R.end()) );

    printf("%lld\n", ans);

    return 0;
}

Submission Info

Judge Result