2015弱校联盟(1) - I. Travel

I. Travel
Time Limit: 3000ms
Memory Limit: 65536KB

The country frog lives in has n towns which are conveniently numbered by 1,2,…,n.

Among n(n−1)/2 pairs of towns, m of them are connected by bidirectional highway, which needs a minutes to travel. The other pairs are connected by railway, which needs b minutes to travel.

Find the minimum time to travel from town 1 to town n.
Input
The input consists of multiple tests. For each test:

The first line contains 4 integers n,m,a,b (2≤n≤10^5,0≤m≤5*10^5,1≤a,b≤10^9). Each of the following m lines contains 2 integers ui,vi, which denotes cities ui and vi are connected by highway. (1≤ui,vi≤n,ui≠vi).

Output
For each test, write 1 integer which denotes the minimum time.
Sample Input

3 2 1 3
1 2
2 3
3 2 2 3
1 2
2 3

Sample Output

2
3

对于(1,n);
(1)如果之间是铁路,则需要判断公路是不是更快
(2)如果是公路,则需要判断铁路是不是更快
分别bfs一次;

#include <bits/stdc++.h>
#define LL long long
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;

const int INF = 0x3f3f3f3f;

const int Max = 1e5+100;

typedef struct node
{
int x;
int num;
} Node;

int n,m;

LL A,B;

LL Dist[Max];

vector<int>Pn[Max];

bool vis[Max];
bool visb[Max];
void init()
{
for(int i=1; i<=n; i++)
    {
        Pn[i].clear();
        vis[i]=false;
    }

}

void bfsa()//公路
{
queue<int>Q;
int b;
    vis[1]=true;
    Dist[n]=INF;
    Dist[1]=0;
    Q.push(1);
while(!Q.empty())
    {
        b=Q.front();
        Q.pop();
int ans = Pn[b].size();
for(int i=0; i<ans; i++)
        {
if(!vis[Pn[b][i]])
            {

if(Dist[b]+A<=B)
                {
                    Dist[Pn[b][i]]=Dist[b]+A;
                    vis[Pn[b][i]]=true;
                    Q.push(Pn[b][i]);
                }
else
                {
return ;
                }
if(Pn[b][i]==n)
                {
return ;
                }
            }
        }
    }
}
void bfsb()//铁路
{
queue<int>Q;
int b;
    Dist[n]=INF;
    Dist[1]=0;
    vis[1]=true;
    Q.push(1);
while(!Q.empty())
    {
        b=Q.front();
        Q.pop();
for(int i=1; i<=n; i++)
        {
            visb[i]=false;
        }
int ans = Pn[b].size();
for(int i=0; i<ans; i++)
        {
            visb[Pn[b][i]]=true;
        }
for(int i=1; i<=n; i++)
        {
if(!visb[i]&&!vis[i])
            {
if(Dist[b]+B<=A)
                {
                    vis[i]=true;
                    Dist[i]=Dist[b]+B;
                    Q.push(i);
                }
else
                {
return ;
                }
if(i==n)
                {
return ;
                }
            }
        }
    }
}

int main()
{
int u,v;
int Dis;
while(~scanf("%d %d %lld %lld",&n,&m,&A,&B))
    {
        init();
        Dis=-1;
for(int i=1; i<=m; i++)
        {
scanf("%d %d",&u,&v);
if((u==1&&v==n)||(u==n&&v==1))
            {
                Dis=A;
            }
            Pn[u].push_back(v);
            Pn[v].push_back(u);
        }
if(Dis==-1)
        {
            bfsa();
printf("%lld\n",min(B,Dist[n]));
        }
else
        {
            bfsb();
printf("%lld\n",min(A,Dist[n]));
        }
    }
return 0;
}