第一行三个整数n, m, R(2 ≤ n ≤ 200, 1 ≤ m ≤ 5000, 2 ≤ R ≤ min(n, 15))。
第二行R个整数表示需要去玩耍的郊区编号。
以下m行每行Ai, Bi, Ci(1 ≤ Ai, Bi ≤ n, Ai ≠ Bi, Ci ≤ 10000)
保证不存在重边。
输出一行表示最小的花费
4 6 3 2 3 4 1 2 4 2 3 3 4 3 1 1 4 1 4 2 2 3 1 6
3
#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; }