郊区春游

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m, R; cin>>n>>m>>R;
    vector<vector<int>> graph(n+1,vector<int>(n+1, INT_MAX));
    vector<int> visit(R+1);
    for(int i=1; i<=R; i++) cin>>visit[i];
    while(m--){
        int u, v, c; cin>>u>>v>>c;
        graph[u][v] = c;
        graph[v][u] = c;
    }
    //Folyd_warshall算法, 求顶点对之间的最短距离
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j){
                    graph[i][j]=0; continue;
                }
                if(graph[i][k]!=INT_MAX&&graph[k][j]!=INT_MAX)
                graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
    // dp[i][j] 为在状态i的条件下,以j为终点的最小花费，那么max(dp[2^R-1][j])即为所求, j\in {1,..,R}
    vector<vector<int>> dp(1<<R, vector<int>(R+1, INT_MAX/2));
    for(int i=0; i<R; i++) dp[1<<i][i+1] = 0; //只有一个顶点时，没有花费
    for(int i=1; i<(1<<R)-1; i++){ //所有状态
        for(int j=1; j<=R; j++){ //在状态i的条件下，以j为终点的最小值已经求出
            if(((1<<(j-1))&i)==0){ //判断在状态i中，j是否可以为终点，即是否已经求过
                continue;
            }
            for(int k=1; k<=R; k++){ //根据dp[i][j],求以k为终点，j为前驱的最小值
                int s = (1<<(k-1))|i; //更新状态，（如果k在状态i时未访问则访问）
                dp[s][k] = min(dp[s][k], dp[i][j]+graph[visit[j]][visit[k]]);
            }
        }
    }
    int res=INT_MAX;
    for(int i=1; i<=R; i++){
        res = min(res, dp[(1<<R)-1][i]);
    }
    cout<<res;
    return 0;
}