1135. 新年好 - AcWing题库

思路： 1.先预处理出1,a,b,c,d,e到其他点的单源最短路，也就是进行6次Dijkstra

            2.计算以1为起点的这6个数的全排列，哪种排列方式所得距离最小，也可以使用dfs

1.Dijkstra+dfs

#define int long longusing namespace std;typedef pair<int,int> PII;constexpr int N =2e5+5;
int dist[6][N];
bool st[50005];
int n,m,h[N],w[N],ne[N],e[N],idx;
int rela[N];
int ans;void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}void Dijkstra(int s, int dist[])
{memset(dist, 0x3f, N*4);//int是4字节，所以大小就是4*Nmemset(st,0,sizeof st);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,s});while(heap.size()){auto [c,t] = heap.top();heap.pop();if(st[t]) continue;st[t]=true;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>c+w[i]){dist[j]=c+w[i];heap.push({dist[j],j});}}}
}int dfs(int u,int num,int dis) 
{if (num==6){return dis;}int ret=0x3f3f3f3f;for (int i=1;i<=5;i++){if (!st[i]){st[i] = 1;ret = min(ret,dfs(i,num+1,dis+dist[u][rela[i]]));st[i] = 0;}}return ret;
}void solve()
{cin>>n>>m;rela[0]=1;for(int i=1;i<=5;i++){cin>>rela[i];}memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=0;i<=5;i++){Dijkstra(rela[i],dist[i]);}memset(st,false,sizeof st);cout<<dfs(0,1,0);
}int32_t main()
{int t;//cin>>t;t=1;while(t--) solve();
}

2.Dijkstra+全排列

#define int long longusing namespace std;typedef pair<int,int> PII;constexpr int N =2e5+5;
int dist[6][N];
bool st[50005];
int n,m,h[N],w[N],ne[N],e[N],idx;
int rela[N],order[6];
int ans;void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}void Dijkstra(int s, int dist[])
{memset(st,0,sizeof st);dist[s]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,s});while(heap.size()){auto [c,t] = heap.top();heap.pop();if(st[t]) continue;st[t]=true;for(int i=h[t];~i;i=ne[i]){int j=e[i];if(dist[j]>c+w[i]){dist[j]=c+w[i];heap.push({dist[j],j});}}}
}void solve()
{memset(dist,0x3f,sizeof dist);cin>>n>>m;order[0]=0;rela[0]=1;for(int i=1;i<=5;i++){order[i]=i;cin>>rela[i];}memset(h,-1,sizeof h);while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c),add(b,a,c);}for(int i=0;i<=5;i++){Dijkstra(rela[i],dist[i]);}memset(st,false,sizeof st);ans=0x3f3f3f3f;do{if(order[0]!=0) break;int sum=dist[0][rela[order[1]]];for(int i=1;i+1<=5;i++)sum+=dist[order[i]][rela[order[i+1]]];ans=min(ans,sum);}while(next_permutation(order,order+6));cout<<ans;
}int32_t main()
{int t;//cin>>t;t=1;while(t--) solve();
}