题目描述
找经过少数点的最短距离之和,顺序任意
样例
输入样例:
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
堆优化的dijkstra+dfs枚举顺序取最小值
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010,M=2e5+10;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],w[M];
int dis[6][N];
bool str[N];
bool str_2[N];
int res=1e18;
int path[10];
int n,m,idx;
void add(int u,int v,int val)
{
e[idx]=v,w[idx]=val,ne[idx]=h[u],h[u]=idx++;
}
void cli(int dis_2[],int u)
{
for(int i=1;i<=n;i++) dis_2[i]=1e18,str[i]=false;
dis_2[u]=0;
priority_queue<PII,vector<PII>,greater<PII>>s;
s.push({0,u});
while(s.size())
{
auto t=s.top();
s.pop();
int id=t.second,distance=t.first;
if(str[id]) continue;
str[id]=true;
// cout<<id<<'\n';
for(int i=h[id];i!=-1;i=ne[i])
{
int j=e[i];
// cout<<j<<endl;
if(dis_2[j]>distance+w[i])
{
dis_2[j]=distance+w[i];
s.push({dis_2[j],j});
}
}
}
}
void dfs(int pre,int cnt,int sum)
{
if(cnt>=5) res=min(res,sum);
for(int i=1;i<=5;i++)
{
if(!str_2[i])
{
str_2[i]=true;
dfs(i,cnt+1,sum+dis[pre][path[i]]);
str_2[i]=false;
}
}
}
void solve()
{
cin>>n>>m;
memset(h,-1,sizeof(h));
path[0]=1;
for(int i=1;i<=5;i++) cin>>path[i];
for(int i=1;i<=m;i++)
{
int u,v,val;
cin>>u>>v>>val;
add(u,v,val),add(v,u,val);
}//预处理出所有点距离1,a,b,c,d的最小距离
// cli(dis[0],1);
for(int i=0;i<=5;i++) cli(dis[i],path[i]);
dfs(0,0,0);
cout<<res<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
while(T--){
solve();
}
return 0;
}
时间复杂度
log(n)