题目描述
固定五个点的情况下求单源最短路
样例
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
21
分析
相当于单源里面套了一个小的最短路
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=5e5+5;
struct mn{
int to,d,nex;
}s[M<<1];
int n,m,net[N],h[N],t;
int q[7],dis[7][N];
queue<int> w;
void add(int a,int b,int c){//建图
s[++t].to=b;
s[t].d=c;
s[t].nex=net[a];
net[a]=t;
}
void init(){//初始化,其实可以删去
while(w.size())
w.pop();
memset(h,0,sizeof(h));
}
void spfa(int x){//spfa
init();
w.push(q[x]),h[q[x]]=1;
dis[x][q[x]]=0;
while(w.size()){
int c=w.front();
w.pop();
for(int i=net[c];i;i=s[i].nex){
int v=s[i].to;
if(dis[x][c]+s[i].d<dis[x][v]){
dis[x][v]=dis[x][c]+s[i].d;
if(!h[v])
w.push(v);
h[v]=1;
}
}
h[c]=0;
}
}
int main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%d %d",&n,&m);
for(int i=1;i<=5;++i)
scanf("%d",&q[i]);
q[0]=1;
int a,b,c;
for(int i=1;i<=m;++i){
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i=0;i<6;++i){
init();
spfa(i);
}
int ans=0x3f3f3f3f;
for(int i=1;i<=5;i++)//非常沙雕的直接杠的写法,dfs,bfs,Floyd都能代替
for(int j=1;j<=5;j++)
for(int l=1;l<=5;l++)
for(int k=1;k<=5;k++)
for(int p=1;p<=5;p++)
if((1<<i) + (1<<j) + (1<<l) + (1<<k) + (1<<p)==62)
ans=min(ans,dis[0][q[i]]+dis[i][q[j]]+dis[j][q[l]]+dis[l][q[k]]+dis[k][q[p]]);
cout<<ans;
return 0;
}
看到五重循环我懵了……
成功TLE 我还以为我写的有问题,没想到来题解区找了找,只要是用spfa的,全都超时了
5重循环太狠了
tle!!
真tm人才
cnm 牛逼呀
好家伙, 这个强!
dp+spfa,活学活用,老哥太强了,膜拜!
tql
tql…
人才
%%%
还不错