题解 | 郊区春游

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

using ll = long long;
const ll INF = (1LL << 60);

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

    int n, m, R;
    if (!(cin >> n >> m >> R)) return 0;

    vector<int> must(R);
    for (int i = 0; i < R; ++i) cin >> must[i];

    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    // 1) 只对 R 个必游点跑 Dijkstra，得到它们之间的两两最短路
    vector<vector<ll>> distR(R, vector<ll>(n + 1, INF));
    auto dijkstra = [&](int srcIdx) {
        int s = must[srcIdx];
        auto& dist = distR[srcIdx];
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        dist[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d != dist[u]) continue;
            for (auto [v, w] : g[u]) {
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
    };
    for (int i = 0; i < R; ++i) dijkstra(i);

    // 构建 R x R 的最短路矩阵
    vector<vector<ll>> w(R, vector<ll>(R, INF));
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < R; ++j)
            w[i][j] = distR[i][ must[j] ];

    // 2) 状态压缩 TSP（开放式路径）：dp[mask][i] 以 i 结尾、走过 mask 的最小代价
    int FULL = (1 << R);
    vector<vector<ll>> dp(FULL, vector<ll>(R, INF));
    for (int i = 0; i < R;
            ++i) dp[1 << i][i] = 0; // 第一段去 V_i 的费用免费（题意）

    for (int mask = 0; mask < FULL; ++mask) {
        for (int i = 0; i < R; ++i) if (dp[mask][i] < INF) {
                for (int j = 0; j < R; ++j) if (!(mask & (1 << j))) {
                        if (w[i][j] >= INF) continue;  // 不连通则跳过
                        int nmask = mask | (1 << j);
                        dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + w[i][j]);
                    }
            }
    }

    ll ans = INF;
    for (int i = 0; i < R;
            ++i) ans = min(ans, dp[FULL - 1][i]); // 最后一段回学校免费
    cout << ans << '\n';
    return 0;
}