题目的主要信息：

• 一共$nn$个点，$mm$条道路连接，每条道路花费会随着道路连接情况给出
• 给出$RR$个要前往的点，前往顺序不定，问什么路线花费最少
• 下面解法中我们用距离代替长度

具体做法：

首先我们用邻接矩阵来表示这个图，矩阵记录两两点之间的距离，初始化为最大值，自己到自己都是0，再根据输入更新直接连接的两个点的距离，然后遍历所有的两两的点，更新所有的点之间的最短距离，得到的点之间的距离都是最短的。

然后我们用$dp[i][j]dp[i][j]$表示状态值为$ii$、以$jj$号地为终点的所有距离最小值，其中状态值是指我们用二进制的形式表示这个地方有没有走过，走过就是1，没走过就是0，一共需要$2^{R}2^R$个位置来表示所有状态，我们用数组代替。

初始化的时候，每个点都是结束，但也只去过这个点，因此自己到自己始终都是0。后续我们枚举所有的状态，对每个状态枚举所有的起始位置和结束位置（需要排除刚刚初始化的位置），然后更新状态： ，其中$ii$为状态，$jj$为起始位置，$kk$为结束位置

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

const int INF = 0x3f3f3f3f;
int main(){
    int n, m, R;
    cin >> n >> m >> R;
    vector<int> visit(R); //需要去的R个郊区
    for(int i = 0; i < R; i++)
        cin >> visit[i];
    vector<vector<int>> edges(n + 1, vector<int>(n + 1, INF)); //邻接矩阵记录边的花费
    for(int i = 1; i <= n; i++)
        edges[i][i] = 0; // 自己到自己是0
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edges[a][b] = c; //构建边的花费
        edges[b][a] = c;
    }
    for(int k = 1; k <= n; k++){ //获取每两两结点间的距离花费
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(edges[i][j] > edges[i][k] + edges[k][j])
                    edges[i][j] = edges[i][k] + edges[k][j]; //更新两两之间的花费为更小的值
            }
        }
    }
    vector<vector<int> > dp(1 << R, vector<int>(R + 1, INF)); 
    for(int i = 0; i < R; i++)
        dp[1 << i][i] = 0; //最开始走的那个，没有花费
    for(int i = 1; i < (1 << R) - 1; i++){ //枚举所有的状态
        for(int j = 0; j < R; j++){ //每个状态的所有起始位置
            if((1 << j) & i == 0) //走过了最开始位置
                continue;
            for(int k = 0; k < R; k++) //更新终点位置
                dp[(1 << k) | i][k] = min(dp[(1 << k) | i][k], dp[i][j] + edges[visit[j]][visit[k]]);
        }
    }
    int mincost = INT_MAX;
    for(int i = 0; i < R; i++) //获取每个位置为结束的最小花费
        mincost = min(mincost, dp[(1 << R) - 1][i]);
    cout << mincost << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n^3+2^R{R}^2)O(n^3+2^RR^2)$，计算所有点之间的最短距离三次遍历为$O(n^3)O(n^3)$，计算最小花费，也是三次遍历，其中最外层与状态数一致，因此为$O(2^R{R}^2)O(2^RR^2)$，其余复杂度都是低次幂
• 空间复杂度：$O(n^2+R{2}^R)O(n^2+R2^R)$，邻接矩阵的大小是$n\ast nn*n$，dp数组的大小是$2^R\ast R2^R*R$