暴力+spfa!!!
这道题,其实可以打暴力!!!
一看题,发现只有5个亲戚,所以就可以全排列出访问亲戚们的顺序.
那么就可以跑6次spfa,处理出每个亲戚访问其他人的最短路,最后每次跑亲戚i到亲戚j的最短路就行了.
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=7;
const int M=5e4+10;
int n;
int tot;
int s[N];
int way[N];
bool vis[M];
int flag[N];
int head[N];
int dis[N][M];
int m,u,v,w,ans=2e9;
queue<int >kano;
struct Edge{
int u,v,w;
}edge[3*N];
inline void add(int x,int y,int z) {
edge[++tot].u=head[x];
edge[tot].v=y;
edge[tot].w=z;
head[x]=tot;
return ;
}
int work() {
int sum=0;
for(int i=1; i<=6; i++) {
sum+=dis[way[i]][s[way[i+1]]];
}
ans=min(sum,ans);
}
void dfs(int x) {
if(x==6) work();
for(int i=2; i<=6; i++) {
if(!flag[i]) {
flag[i]=1;
way[x+1]=i;
dfs(x+1);
flag[i]=0;
way[x+1]=0;
}
}
}
void spfa(int i) {
while(!kano.empty()) kano.pop();
for(int j=1; j<=n; j++) dis[i][j]=1e8;
for(int j=1; j<=n; j++) vis[j]=0;
kano.push(s[i]);
dis[i][s[i]]=0;
vis[s[i]]=1;
while(!kano.empty()) {
int now=kano.front();
kano.pop();
vis[now]=0;
for(int k=head[now]; k; k=edge[k].u) {
int to=edge[k].v,pay=edge[k].w;
if(dis[i][now]+pay<=dis[i][to]) {
dis[i][to]=dis[i][now]+pay;
if(!vis[to]) {
kano.push(to);
vis[to]=1;
}
}
}
}
}
int main() {
cin>>n>>m;
s[1]=1;
way[1]=1;
for(int i=2; i<=6; i++) cin>>s[i];
for(int i=1; i<=m; i++) {
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=1; i<=6; i++) {
spfa(i);
}
dfs(1);
cout<<ans;
}
楼主写的不错,我用dijkstra写了一下,给有需要的同学参考一下
https://www.acwing.com/solution/content/42071/
欢迎相互交流。
Segmentation Fault 了
hh