时间限制: 1000 ms 内存限制: 65536 KB
提交数: 535 通过数: 295
【题目描述】
原题来自:CQOI 2005

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

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

【输入】
第一行:n,m 为车站数目和公路的数目。

第二行:a,b,c,d,e 为五个亲戚所在车站编号。

以下 m 行,每行三个整数 x,y,t,为公路连接的两个车站编号和时间。

【输出】
输出仅一行,包含一个整数 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
【输出样例】
21
【提示】
数据范围:

对于全部数据,1≤n≤50000,1≤m≤105,1<a,b,c,d,e≤n,1≤x,y≤n,1≤t≤100。

#include <iostream>
#include <cstring>
#include <queue>

#define N 51200
#define M 102400
using namespace std;

struct Edge
{
    int to,dis,next;
} edge[M*2];

int head[N],deg;

int n,m;

int way[6];

inline void add(int from,int to,int dis)
{
    edge[++deg].next=head[from];
    edge[deg].to=to;edge[deg].dis=dis;
    head[from]=deg;
}

inline void init()
{
    cin.tie(0);
    cin>>n>>m;
    
    way[0]=1;    //自己 
    
    for(int i=1;i<=5;i++)
        cin>>way[i];

    
    for(int i=1;i<=m;i++)
    {
        int f,t,d;
        cin>>f>>t>>d;
        add(f,t,d);add(t,f,d);
    }
}

int dist[N];bool ved[N];

inline int dis(int from,int to)
{
    memset(dist,0x3f,sizeof(dist));
    memset(ved,0,sizeof(ved));
    queue <int> Q;
    
    Q.push(from);
    ved[from]=true;
    
    dist[from]=0;
    
    while(!Q.empty())
    {
        int k=Q.front();
        Q.pop();
        ved[k]=false;
        
        for(int i=head[k];i!=0;i=edge[i].next)
            if( dist[edge[i].to]> dist[k]+edge[i].dis)
            {
                dist[edge[i].to]=dist[k]+edge[i].dis;
                if(!ved[edge[i].to])
                {
                    Q.push(edge[i].to);
                    ved[edge[i].to]=true;
                }
            }
    }
    return dist[to];
}

int G6;

int minn=0x7f7f7f7f;

void dfs(int n,int k,int z)
{
    if(z==6)
    {
        minn=min(minn,k);
        return;    
    }
    for(int i=1;i<=5;i++)
        if(!ved[i])
        {
            ved[i]=true;
            dfs(i,k+Gn,z+1);
            ved[i]=false;
        }
}


int main()
{
    init();
    //计算各个亲戚之间的距离,化大为小
    for(int i=0;i<6;i++)
        for(int j=0;j<6;j++)
            if(Gi==0)    //避免重复计算 
                Gj=Gi=dis(way[i],way[j]);
    
    memset(ved,0,sizeof(ved));
    
    dfs(0,0,1);
    cout<<minn;
}

Last modification:February 7th, 2021 at 03:14 pm