【刷题】【最短路】新年好

重庆城里有n个车站，m条双向公路连接其中的某些站。每两个车站最多用一条公路直接相连，从任何一个车站出发都可以经过一条或多条公路到达其它车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间和。

佳佳的家在车站1，他有五个亲戚，分别住在车站a、b、c、d、e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

用最短路算法，求出5个点分别的距离，和1到五个点的距离，

然后枚举完事

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
const int N=5e4+3,M=1e5+3;
int tot,head[N];
struct node
{
    int v,w,nx;
}e[M<<1];
void add(int u,int v,int w)
{
    e[++tot].v =v,e[tot].w =w,e[tot].nx =head[u],head[u]=tot;
    e[++tot].v =u,e[tot].w =w,e[tot].nx =head[v],head[v]=tot;
}
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}

int dis[N]; bool in[N];
int pt[6],dd[6][6];
struct nd
{
    int v;
    bool operator < (const nd & o) const
    { return dis[v] > dis[o.v]; }
    nd(int vv)
    { v=vv; }
    nd(){}
};
priority_queue <nd> q;
void dijk(int st,int k)
{
    while(!q.empty() ) q.pop() ;
    memset(dis,0x3f,sizeof(dis));
    memset(in,false,sizeof(in));
    dis[st]=0,q.push(nd(st));

    while(!q.empty() )
    {
        int nw=q.top() .v;q.pop() ;

        for(int i=head[nw];i;i=e[i].nx )
        {
            int nx=e[i].v ;
            if(dis[nx]>dis[nw]+e[i].w )
            {
                dis[nx]=dis[nw]+e[i].w ;
                if(!in[nx])
                    in[nx]=true,q.push(nd(nx));
            }
        }
        in[nw]=false;
    }

    for(int i=1;i<=5;i++)
        dd[k][i]=dis[pt[i]];
}

bool us[6];int ans=1<<30;
void dfs(int cnt,int sum,int pre)
{
    if(sum>ans) return ;
    if(cnt==5)
    {
        ans=min(ans,sum);
        return ;
    }

    for(int i=1;i<=5;i++)
    {
        if(us[i]) continue;
        us[i]=true;
        dfs(cnt+1,sum+dd[pre][i],i);
        us[i]=false;
    }
}

int main()
{
    n=read(),m=read();
    pt[0]=1;
    for(int i=1;i<=5;i++)
        scanf("%d",&pt[i]);
    int u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        add(u,v,w);
    }

    for(int i=0;i<=5;i++)
        dijk(pt[i],i);
    dfs(0,0,0);
    printf("%d\n",ans);

    return 0;
}

View Code