HDU 3768 Shopping：旅行商問題 (狀態壓縮 DP + SPFA)

問題描述

城市有 N 個路口（0..N-1，0 為家），M 條雙向道路（長度 D）。有 S 個商店（1 ≤ S ≤ 10）分別位於某些路口。需從家出發，拜訪所有商店並返回家，求最短總路程。多測試用例。

解題思路：兩階段

1. 全對最短路：關鍵點集合 = {家} ∪ {商店}，共 K = S+1 ≤ 11 個點。對每個關鍵點跑一次 SPFA（或 Dijkstra），得到關鍵點之間的最短距離 dist[u][v]。
2. 狀態壓縮 DP (TSP)：狀態 dp[mask][i] 表示已拜訪商店集合 mask（bitmask，S 位），當前位於第 i 個關鍵點（0=家，1..S=商店）的最短路徑長。
   • 初始：dp[1<<i][i] = dist[0][i]（從家直接去商店 i）。
   • 轉移：dp[mask | (1<<j)][j] = min(dp[mask][i] + dist[i][j])，對所有 i ∈ mask, j ∉ mask。
   • 答案：min_i dp[(1<<S)-1][i] + dist[i][0]（回家）。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100005;
const int MAXS = 10;

struct Edge { int to, w; };
vector<Edge> g[MAXN];
int dis[MAXN], inq[MAXN];
int keyDist[12][12];  // 關鍵點間最短距離
int dp[1<<12][12];
int store[12];        // 關鍵點對應的原圖節點編號

void spfa(int s, int n) {
    fill(dis, dis+n+1, INF);
    fill(inq, inq+n+1, 0);
    queue<int> q;
    dis[s] = 0; q.push(s); inq[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto &e : g[u]) {
            int v = e.to;
            if (dis[v] > dis[u] + e.w) {
                dis[v] = dis[u] + e.w;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; ++i) g[i].clear();
        for (int i = 0; i < m; ++i) {
            int x, y, d; scanf("%d%d%d", &x, &y, &d);
            g[x].push_back({y, d});
            g[y].push_back({x, d});
        }
        int S; scanf("%d", &S);
        store[0] = 0;  // 家
        for (int i = 1; i <= S; ++i) scanf("%d", &store[i]);
        // 計算關鍵點兩兩最短路
        for (int i = 0; i <= S; ++i) {
            spfa(store[i], n);
            for (int j = 0; j <= S; ++j)
                keyDist[i][j] = dis[store[j]];
        }
        // TSP DP
        int ALL = (1 << (S+1)) - 1;  // 包含家的 bit，但家不需拜訪
        // 實際只需拜訪 S 個商店，mask 只用 S 位
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 1; i <= S; ++i)
            dp[1<<(i-1)][i] = keyDist[0][i];
        for (int mask = 0; mask < (1<