因为不太习惯枚举所以整了个状压dp代替.....
C++ 代码
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>edges[50001];
map<int, map<int, int>>dst;
int dis[50001];//仅用于dij函数中
int n, m, vis[50001], rel[5], memo[5][1 << 5];
//memo[i][k]表示当前位于第i个亲戚处,拜访状态为k时的最短距离
struct node {
int num, dst;
friend bool operator<(node a, node b) {
return a.dst > b.dst;
}
};
int dfs(int now, int state) {//记忆化搜索
if (memo[now][state] >= 0) return memo[now][state];
int res = INT_MAX / 2;
for (int i = 0; i < 5; i++) {
if (i == now || (state & (1 << i)) == 0) continue;
res = min(res, dfs(i, state ^ (1 << now)) + dst[rel[i]][rel[now]]);
}
return memo[now][state] = res;
}
void dij(int start, int end) {
priority_queue<node>nodes;
memset(dis,0x3f,sizeof dis);
memset(vis, 0, sizeof vis);
nodes.push(node{ start,0 });
dis[start]=0;
while (!nodes.empty()) {
node temp = nodes.top();
nodes.pop();
if (vis[temp.num] == 1) continue;
else vis[temp.num] = 1;
if (temp.num == end) {
dst[start][end] = dst[end][start] = temp.dst;
break;
}
for (int i = 0; i < edges[temp.num].size(); i++) {
int t = edges[temp.num][i].first, len = edges[temp.num][i].second;
if(dis[t]>dis[temp.num]+len){
dis[t]=dis[temp.num]+len;
nodes.push(node{ t,temp.dst + len });
}
}
}
return;
}
int main() {
cin >> n >> m;
memset(memo, -1, sizeof memo);
for (int i = 0; i < 5; i++) {
cin >> rel[i];
}
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
edges[x].push_back({ y,z });
edges[y].push_back({ x,z });
}
for (int i = 0; i < 5; i++) {
dij(1, rel[i]);
for (int k = i + 1; k < 5; k++) {
dij(rel[i], rel[k]);
}
memo[i][1 << i] = dst[1][rel[i]];
}
int res = INT_MAX / 2;
for (int i = 0; i < 5; i++) {
res = min(res, dfs(i, (1 << 5) - 1));
}
cout << res;
return 0;
}