更好的阅读体验

题意：求从1出发经过给定的条关键路径回到1的最短路，

注意到条边的两个端点，再加上起点1，只有这些点是关键点，其他的点都无关紧要

预处理出每两个关键点之间的最短路，然后类似于旅行者问题跑一个状压dp，讨论一下每个关键路径的两个端点转移即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define mp(x, y) make_pair(x, y)

using namespace std;

const int N = 1e6 + 10, M = 2e5 + 10;

const long long inf = 1e18;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {
    int u, v, nxt, dis;
} edge[N];

int n, m, B, u[N], v[N], t[N], head[N], cnt;

long long dis[20][20][2][2], d[N], back[N][2], dp[N][12][2];

bool vis[N];

void add(int u, int v, int t) {edge[++cnt] = (EDGE){u, v, head[u], t}; head[u] = cnt;}

void gmin(long long &x, long long y) {x = min(x, y);}

priority_queue<pair<long long, int> >q;

void dij(int s) {
    memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); d[s] = 0; q.push(mp(0, s));
    while (!q.empty()) {
        int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = 1;
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v, t = edge[e].dis;
            if (d[u] + t < d[v]) {
                d[v] = d[u] + t; q.push(mp(-d[v], v));
            }
        }
    }
}

int main() {
    n = read(); m = read(); B = read();
    for (int i = 0; i < m; i++) {
        u[i] = read(); v[i] = read(); t[i] = read();
        add(u[i], v[i], t[i]); add(v[i], u[i], t[i]);
    }
    for (int i = 0; i < B; i++) {
        dij(u[i]);
        for (int j = 0; j < B; j++) {
            dis[i][j][0][0] = d[u[j]]; dis[i][j][0][1] = d[v[j]];
        }
        back[i][0] = d[1]; dij(v[i]);
        for (int j = 0; j < B; j++) {
            dis[i][j][1][0] = d[u[j]]; dis[i][j][1][1] = d[v[j]];
        }
        back[i][1] = d[1];
    }
    memset(dp, 0x3f, sizeof(dp)); dij(1);
    for (int i = 0; i < B; i++) {
        dp[1 << i][i][0] = d[v[i]] + t[i];
        dp[1 << i][i][1] = d[u[i]] + t[i];
    }
    for (int s = 1; s < 1 << B; s++) {
        for (int i = 0; i < B; i++) if (1 << i & s) {
            for (int j = 0; j < B; j++) if (!(1 << j & s)) {
                gmin(dp[s | 1 << j][j][1], dp[s][i][0] + dis[i][j][0][0] + t[j]);
                gmin(dp[s | 1 << j][j][0], dp[s][i][0] + dis[i][j][0][1] + t[j]);
                gmin(dp[s | 1 << j][j][1], dp[s][i][1] + dis[i][j][1][0] + t[j]);
                gmin(dp[s | 1 << j][j][0], dp[s][i][1] + dis[i][j][1][1] + t[j]);
            }
        }
    }
    long long ans = inf;
    for (int i = 0; i < B; i++) {
        gmin(ans, dp[(1 << B) - 1][i][0] + back[i][0]);
        gmin(ans, dp[(1 << B) - 1][i][1] + back[i][1]);
    }
    printf("%lld", ans);
    return 0;
}