[南海云课堂] [最短路模板] 拜年

_Cheems · 2023-08-08 22:07:47 · 个人记录

题意

某城里有 n 个车站，m 条双向道路连接其中的某些车站。

每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 1，他有五个亲戚，分别住在车站 a，b，c，d，e。

过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。

怎样走，才需要最少的时间？

思路

最短路径由起点、终点的不同，可分为两部分：

1. 佳佳 -> 亲戚。

2. 亲戚 -> 亲戚。

对于 1：跑一遍源点为 1 的最短路即可。

对于 2：由于亲戚数量固定为 5，因此以不同亲戚为起点，跑 4 次单源最短路即可（最后一个亲戚不用跑）。

预处理后，直接全排列暴力枚举访问次序，并取最小值。

考虑使用堆优化的 \rm{Dijkstra}。时间复杂度：O(mlogn)，常数为 5，故可通过。

代码

#include<bits/stdc++.h>
using namespace std;
#define pir pair<int,int>
const int N=5e4+5,M=1e6+5;
int n,m,u,v,w,a,b,c,d,ee,dis[N],vis[N],head[N],cnt,ans;
int jj[15],qq[15][15],f[15];
struct edge{
    int v,w,nxt;
}e[2*M];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dj(int k){
    priority_queue<pir,vector<pir>,greater<pir>>q;
    memset(dis,0x3f,sizeof(dis)); 
    memset(vis,0,sizeof(vis)); 
    dis[k]=0; 
    q.push({0,k}); 
    while(!q.empty()){ 
        int s=q.top().first; 
        int k=q.top().second; 
        q.pop(); 
        if(vis[k]){ 
            continue;
        }
        vis[k]=1; 
        for(int i=head[k]; i;i=e[i].nxt){
            int j=e[i].v;
            if(!vis[j]&&dis[k]+e[i].w<dis[j]){ 
                dis[j]=dis[k]+e[i].w;
                q.push({dis[j],j});
            }
        }
    }
}
void insert(int u,int v,int w){
    qq[u][v]=qq[v][u]=w;
}
void zsw(){
    dj(1);
    jj[1]=dis[a];
    jj[2]=dis[b];
    jj[3]=dis[c];
    jj[4]=dis[d];
    jj[5]=dis[ee];
    dj(a);
    insert(1,2,dis[b]);
    insert(1,3,dis[c]);
    insert(1,4,dis[d]);
    insert(1,5,dis[ee]);
    dj(b);
    insert(2,3,dis[c]);
    insert(2,4,dis[d]);
    insert(2,5,dis[ee]);
    dj(c);
    insert(3,4,dis[d]);
    insert(3,5,dis[ee]);
    dj(d);
    insert(4,5,dis[ee]);
}
void dfs(int fhr,int tot,int sum){
    if(tot==5){
        ans=min(ans,sum);
        return ;
    }
    for(int i=1; i<=5;i++){
        if(!f[i]){
            f[i]=1;
            dfs(i,tot+1,sum+qq[fhr][i]);
            f[i]=0;
        }
    }
}
int main(){
    scanf("%d%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d,&ee);
    for(int i=1; i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v){
            continue;
        }
        add(u,v,w);
        add(v,u,w);
    }

    zsw();
    ans=0x3f3f3f3f;

    for(int i=1; i<=5;i++){
        f[i]=1;
        dfs(i,1,jj[i]);
        f[i]=0;
    }
    cout<<ans;
    return 0;
}