【小码匠自习室】摸鱼被抓：ABC 073 - D - joisino's travel

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

4

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

3

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
 
void best_coder() {
    int n, m, r;
    cin >> n >> m >> r;
    vector<vector<int>> g(n, vector<int>(n, 1e9));
    vector<int> l(r);
    for (int i = 0; i < r; ++i) {
        cin >> l[i];
        --l[i];
    }
    sort(l.begin(), l.end());
    for (int i = 0; i < m; ++i) { //存储边的情况
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        g[u][v] = w;
        g[v][u] = w;
    }
    for (int i = 0; i < n; ++i) {
        g[i][i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j == i) {
                continue;
            }
            for (int s = 0; s < n; ++s) {
                if (s == i || s == j) {
                    continue;
                }
                g[j][s] = min(g[j][s], g[i][s] + g[j][i]);
            }
        }
    }
    int ans = 1e9;
    do {
        int cnt = 0;
        for (int i = 0; i < r - 1; ++i) {
            cnt += g[l[i]][l[i + 1]];
        }
        ans = min(cnt, ans);
    } while (next_permutation(l.begin(), l.end()));
    cout << ans;
}
 
void happy_coder() {
}
 
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    // 小码匠
    best_coder();
 
    // 最优解
    // happy_coder();
 
    // 返回
    return 0;
}