CJOI 05新年好 (最短路+枚举)

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

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

输入

　第一行：n(n<=50,000),m(m<=100,000)为车站数目和公路的数目。

第二行：a,b,c,d,e，为五个亲戚所在车站编号（1<a,b,c,d,e<=n）。

以下m行，每行三个整数x,y,t（1<=x,y<=n,1<=t<=100）,为公路连接的两个车站编号和时间。

输出

　仅一行，包含一个整数T，为最少的总时间

样例输入

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

样例输出

解题报告

必须经过a,b,c,d,e这几个点，故我们必须知道包括起点在内的6个点的最短路。所以跑6遍堆优dijkstra。最后再对a,b,c,d,e的顺序进行全排列，计算结果取最小即可。

复杂度O(6*nlogn)

#include<bits/stdc++.h>

#define Pair pair<int,int>

#define MAXN 70000+10

#define MAXM 200000+10

using namespace std;

struct Edge{

    int next,to,dis;

}edge[MAXM];

int n,m,num,v[MAXN],dis[MAXN],head[MAXN];

int disi[][MAXN],u[MAXN],ans=,a[],b[];

int temp=;

void add(int from,int to,int dis)

{

    edge[++num].next=head[from];

    edge[num].to=to;

    edge[num].dis=dis;

    head[from]=num;

}

void dij(int s)

{

    memset(v,,sizeof(v));

    priority_queue<Pair,vector<Pair>,greater<Pair> > h;

    for(int i=;i<=n;i++) disi[s][i]=;

    disi[s][u[s]]=;

    h.push(Pair(,u[s]));

    while(h.size()>)

    {

        int k=h.top().second;h.pop();

        if(v[k]) continue;

        v[k]=;

        for(int i=head[k];i;i=edge[i].next)

        if(disi[s][edge[i].to]>disi[s][k]+edge[i].dis)

        {

            disi[s][edge[i].to]=disi[s][k]+edge[i].dis;

            h.push(Pair(disi[s][edge[i].to],edge[i].to));

        }

    }

}

void dfs(int x)

{

    for(int i=;i<=;i++)

    if(!b[i])

    {

        b[i]=;

        a[x]=i;

        if(x==)

        {

            temp=;

            for(int i=;i<;i++)

                temp+=disi[a[i]][u[a[i+]]];

            ans=min(ans,temp);

            temp=;

        }else dfs(x+);

        b[i]=;

        a[x]=;

    }

}

int main()

{

    freopen("newyear.in","r",stdin);

    freopen("newyear.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=;i++)

        scanf("%d",&u[i]);

    for(int i=;i<=m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);

        add(y,x,z);

    }

    u[]=;

    for(int i=;i<=;i++)

        dij(i);

    a[]=;

    dfs();

    printf("%d\n",ans);

    return ;

}

巴特西

CJOI 05新年好 (最短路+枚举)

CJOI 05新年好 (最短路+枚举)

最新文章

热门文章