SCU 4444: Travel(最短路)

时间：2021-09-19 16:39:00

Travel

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≤105,0≤m≤5⋅105,1≤a,b≤109). 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. 1到 n 铁路可以直连 跑一次最短路取 Min(b,dist[n])
2. 1 到n 高速公路连通 那么我们BFS跑最短路 ,每次构一次新图,每个点入队一次.因为是完全图所以每次可以入队的点都非常多.所以可以暴力.

#include <iostream>

#include <cstdio>

#include <string.h>

#include <queue>

#include <algorithm>

#include <math.h>

using namespace std;

typedef long long LL;

const LL INF = 1e16;

const LL N = ;

struct Edge{

    LL v,next;

    LL w;

}edge[*N];

LL head[N];

LL tot,n,m,a,b;

bool vis[N];

LL low[N];

LL MIN ;

void addEdge(LL u,LL v,LL w,LL &k){

    edge[k].v = v,edge[k].w = w,edge[k].next = head[u],head[u]=k++;

}

struct Node{

    int u;

    int step;

};

void init(){

    memset(head,-,sizeof(head));

    tot = ;

}

void spfa(LL pos){

    for(LL i=;i<=n;i++){

        low[i] = INF;

        vis[i] = false;

    }

    low[pos] = ;

    queue<LL>q;

    while(!q.empty()) q.pop();

    q.push(pos);

    while(!q.empty()){

        LL u = q.front();

        q.pop();

        vis[u] = false;

        for(LL k=head[u];k!=-;k=edge[k].next){

            LL w = edge[k].w,v = edge[k].v;

            if(low[v]>low[u]+w){

                low[v] = low[u]+w;

                if(!vis[v]){

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

}

bool vis1[N];

int bfs(int pos){

    memset(vis,,sizeof(vis));

    queue<Node> q;

    Node node;

    vis[pos] = ;

    node.u = pos;

    node.step = ;

    q.push(node);

    while(!q.empty()){

        memset(vis1,false,sizeof(vis1));

        node = q.front();

        int u = node.u;

        int step = node.step;

        /// if((step+1)*b>a) return -1;  TLE

        q.pop();

        vis1[u] = ;

        for(int k=head[u];k!=-;k=edge[k].next){

            int v = edge[k].v;

            vis1[v] = true;

        }

        Node next;

        if(!vis1[n]) return step+;

        for(int i=n;i>=;i--){

            if(!vis1[i]&&!vis[i]){

                if((step+)*b>a) return -;

                next.u = i;

                next.step = step+;

                q.push(next);

                vis[i] = true;

            }

        }

    }

    return -;

}

int main(){

    while(scanf("%lld%lld%lld%lld",&n,&m,&a,&b)!=EOF){

        init();

        bool flag = false;

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

            LL u,v;

            scanf("%lld%lld",&u,&v);

            addEdge(u,v,a,tot);

            addEdge(v,u,a,tot);

            if(u==&&v==n||u==n&&v==) flag = ;

        }

        LL ans = ;

        if(!flag){

            spfa();

            ans = min(low[n],b);

        }else{

            int step = bfs();

            if(step==-) ans = a;

            else ans = min(a,step*b);

        }

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

    }

}

相关文章