今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区Ai和Bi，路费是Ci。经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V1, V2 ,V3 … VR，那么他们的总花费为从V1到V2的花费加上V2到V3的花费依次类推，注意从铁子班上到V1的花费和从VR到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。

区块链毕设网qklbishe.com为您提供问题的解答

今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区A_i和B_i，路费是C_i。经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V₁, V₂,V₃… V_R，那么他们的总花费为从V₁到V₂的花费加上V₂到V₃的花费依次类推，注意从铁子班上到V₁的花费和从V_R到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。

#include <bits/stdc++.h>

#define INFI 9999999

#define FIO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

usingnamespacestd;

typedeflonglongintll;

intn, m, place_num, road[209][209], want_go[20];

ll dp[1 << 15][20], ans;

intmain() {

FIO;

cin >> n >> m >> place_num;

//place_num总共想要去的地点数

for(inti = 1; i <= place_num; i++) {

cin >> want_go[i];

}

//初始化不同点之间的距离为无穷大

for(inti = 1; i <= n; i++) {

for(intj = 1; j <= n; j++) {

if(i != j) {

road[i][j] = INFI;

}

inta, b, c;

for(inti = 1; i <= m; i++) {

cin >> a >> b >> c;

road[a][b] = min(road[a][b], c);

road[b][a] = road[a][b];

}

//Floyd求最短路

for(inti = 1; i <= n; i++) {

for(intj = 1; j <= n; j++) {

for(intk = 1; k <= n; k++) {

road[j][k] = min(road[j][k], road[j][i] + road[i][k]);

}

//初始化dp数组

memset(dp, INFI,sizeof(dp));

for(inti = 1; i <= place_num; i++) {

dp[1 << (i – 1)][i] = 0;

}

for(inti = 1; i < (1 << place_num) – 1; i++) {

//转换成二进制，1表示已经去了该地点，0表示没有去过该地点

for(intj = 1; j <= place_num; j++) {

if(i & (1 << (j – 1))) {//i的二进制的第j位为1，即已经去了第j个顶点

//那么我们就可用当前的数据去更新还未去的地点的数据

for(intk = 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(inti = 1; i <= place_num; i++) {

ans = min(ans, dp[(1 << place_num) – 1][i]);

}

cout << ans << endl;

return0;

}

54:42

以上就是关于问题今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区Ai和Bi，路费是Ci。经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V1, V2 ,V3 … VR，那么他们的总花费为从V1到V2的花费加上V2到V3的花费依次类推，注意从铁子班上到V1的花费和从VR到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训