郊区春游

难度：5星

解法1

我们设 $dp[i][j]dp[i][j]$ 为 状态值为 $ii$ ，并以 $jj$ 号地点为终点的路程最小值。其中状态值是指每个地点是否走过的状态的二进制，1代表走过，0代表没走过。那么转移方程是：

，其中 $g[j][k]g[j][k]$ 为 $jj$ 到 $kk$ 的最短路。转移可以用bfs来实现，这样保证会优先检查走过较少地点的状态，然后慢慢转移到走过较多地点的状态。

所有点的点对之间的最短路可以用floyd解决，复杂度 $O(n^3)O(n^3)$ ，状压dp的复杂度为 $O(2^r\ast r)O(2^r*r)$。

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

const int INF = 1e9+7;
int g[210][210] , n , m , go[20] , r , dp[1<<16][20];

void floyd() {
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            for (int k = 1 ; k <= n ; k ++) {
                if (g[i][k]+g[i][j] < g[k][j]) g[k][j] = g[i][k]+g[i][j];
            }
        }
    }
}

struct Node {
    int sta, crt , cost;
};
int main() {
    scanf("%d%d%d",&n,&m,&r);
    for (int i = 0 ; i < r ; i ++) {
        scanf("%d",&go[i]);
    }
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            g[i][j] = INF;
        }
        g[i][i] = 0;
    }
    for (int i = 1 ; i <= m ; i ++) {
        int s , t , v;
        scanf("%d%d%d",&s,&t,&v);
        g[s][t] = v;
        g[t][s] = v;
    }
    floyd();

    memset(dp,0x3f3f3f,sizeof dp);
    deque<Node >dq;
    int res = INF;
    for (int i = 0 ; i < r ; i ++) {
        dq.push_back({(1<<i),i,0});
        dp[1<<i][i]=0;
    }
    while (!dq.empty()) {
        auto temp = dq.front();
        dq.pop_front();
        if (temp.sta == (1<<r)-1) continue;
        for (int i = 0 ; i < r ; i ++) {
            
            if (((temp.sta & (1<<i)) == 0) && temp.cost+g[go[i]][go[temp.crt]] < dp[temp.sta|(1<<i)][i]) {
                dp[temp.sta|(1<<i)][i]=temp.cost+g[go[i]][go[temp.crt]];
                dq.push_back({(temp.sta|(1<<i)),i,dp[temp.sta|(1<<i)][i]});
            }
        }
    }
    for(int i=0;i<r;i++){
        res=min(res,dp[(1<<r)-1][i]);
    }
    printf("%d\n",res);
}

解法2

先使用 floyd 算法得出各点之间的最短距离。

我们使用状态压缩的动态规划，由于一共有最多 $1515$ 个点需要遍历，因此有 $2^{15}2^\{15\}$ 个状态需要记录。每个状态码的第 $ii$ 二进制位的 $00$ 和 $11$ 分别表示第 $ii$ 点是否已经遍历。

设 $dp[i][j]dp[i][j]$ 表示状态码是 $ii$ 时最后一次到达 $jj$ 点时最少花费是多少。

我们枚举此题中的所有状态码 $ii$ 和当前状态码下的所有可能起点 $jj$ 和终点 $kk$ 因此可得状态转移方程 $dp[i+2^k][k]=min(dp[i+2^k][k],dp[i][j]+dis[j][k])dp[i+2^k][k]\; =\; min(dp[i+2^k][k],dp[i][j]+dis[j][k])$ （当 $jj$ 在此状态码中已包含且 $kk$ 不在此状态码中）。然后遍历最终状态（已经过路线上中每个点）的所有可能终点的最小值 $min(dp[(2^r-1)][i])min(dp[(2^r-1)][i])$ 即为答案。

#include<bits/stdc++.h>
#define ll long long
// #define int ll
using namespace std;

const int INF = 1e9+7;
//g-邻接矩阵  go-映射路线上第i个点实际是第几个点  dp[i][j]-i-状态码-j-终点
int g[210][210] , n , m , go[20] , r , dp[1<<16][210];

void floyd() {
    for (int k = 1 ; k <= n ; k ++) {
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1;  j <= n ; j ++) {
                if (g[i][k]+g[k][j] < g[i][j]) g[i][j] = g[i][k]+g[k][j];
            }
        }
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&r);
    for (int i = 0 ; i < r ; i ++) {
        scanf("%d",&go[i]);
    }
    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            g[i][j] = INF;
        }
        g[i][i] = 0;
    }
    for (int i = 1 ; i <= m ; i ++) {
        int s , t , v;
        scanf("%d%d%d",&s,&t,&v);
        g[s][t] = min(v,g[s][t]);
        g[t][s] = g[s][t];
    }
    floyd();
    memset(dp,0x3f3f3f,sizeof dp);
    int res = INF;
    // 从路线上第i个点出发，由题意从此步费用是0
    for (int i = 0 ; i <r ; i ++) dp[(1<<i)][go[i]] = 0;

    //遍历状态
    for (int i = 1 ; i < (1<<r)-1 ; i ++) {
        //起点j
        for (int j = 0 ; j < r ; j ++) {
            //保证j一定在i状态中
            if ((1<<j)&i) {
                for (int k = 0 ; k < r ; k ++) {
                    //保证k在此状态下没有被遍历过
                    if (!((1<<k)&i)) {
                        dp[i|(1<<k)][go[k]] = min(dp[i][go[j]]+g[go[j]][go[k]],dp[i|(1<<k)][go[k]]);
                    }
                }
            }
        }
    }
    for (int i = 0 ; i < r ; i ++) res = min(res,dp[(1<<r)-1][go[i]]);
    printf("%d\n",res);
}