有详细注释
#include <bits/stdc++.h> #define INFI 9999999 #define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using namespace std; typedef long long int ll; int n, m, place_num, road[209][209], want_go[20]; ll dp[1 << 15][20], ans; int main() { FIO; cin >> n >> m >> place_num; //place_num总共想要去的地点数 for (int i = 1; i <= place_num; i++) { cin >> want_go[i]; } //初始化不同点之间的距离为无穷大 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { road[i][j] = INFI; } } } int a, b, c; for (int i = 1; i <= m; i++) { cin >> a >> b >> c; road[a][b] = min(road[a][b], c); road[b][a] = road[a][b]; } //Floyd求最短路 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { road[j][k] = min(road[j][k], road[j][i] + road[i][k]); } } } //初始化dp数组 memset(dp, INFI, sizeof(dp)); for (int i = 1; i <= place_num; i++) { dp[1 << (i - 1)][i] = 0; } for (int i = 1; i < (1 << place_num) - 1; i++) { //转换成二进制,1表示已经去了该地点,0表示没有去过该地点 for (int j = 1; j <= place_num; j++) { if (i & (1 << (j - 1))) {//i的二进制的第j位为1,即已经去了第j个顶点 //那么我们就可用当前的数据去更新还未去的地点的数据 for (int k = 1; k <= place_num; k++) { if ((i & (1 << (k - 1))) == 0) {//i的二进制的第k位为0 dp[i + (1 << (k - 1))][k] = min(dp[i + (1 << (k - 1))][k], dp[i][j] + road[want_go[j]][want_go[k]]); //dp数组第一维存储i,记录了当前已经去了和没去的地点 //第二维存储当前走法的最后到达的位置 } } } } } ans = INFI; for (int i = 1; i <= place_num; i++) { ans = min(ans, dp[(1 << place_num) - 1][i]); } cout << ans << endl; return 0; }