HDU Victor and World：Floyd + 狀態壓縮 DP 解 TSP

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[18][18];
int dp[1<<17][17];

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dist[i][j] = (i==j?0:INF);
        for (int i = 0; i < m; ++i) {
            int u, v, w; cin >> u >> v >> w; --u; --v;
            dist[u][v] = dist[v][u] = min(dist[u][v], w);
        }
        // Floyd
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        // DP
        int ALL = 1 << n;
        for (int mask = 0; mask < ALL; ++mask)
            for (int i = 0; i < n; ++i)
                dp[mask][i] = INF;
        dp[1][0] = 0;
        for (int mask = 1; mask < ALL; ++mask) {
            for (int i = 0; i < n; ++i) if (mask & (1<