时间戳

首页 > 技术文章 > SCU 4444 Travel （补图最短路）

SCU 4444 Travel （补图最短路）

jianrenfang 2017-05-01 10:47 原文

Travel

The country frog lives in has \(n\) towns which are conveniently numbered by \(1, 2, \dots, n\).

Among \(\frac{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 \leq n \leq 10^5, 0 \leq m \leq 5 \cdot 10^5, 1 \leq a, b \leq 10^9\)). Each of the following \(m\) lines contains \(2\) integers \(u_i, v_i\), which denotes cities \(u_i\) and \(v_i\) are connected by highway. (\(1 \leq u_i, v_i \leq n, u_i \neq v_i\)).

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
【分析】补图最短路。每个点只放进队列一次，set维护。
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define met(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N = 1e6+5;
int n,m,k;
set<int>s,t;
set<int>::iterator it;
vector<int>edg[N];
int vis[N];
ll dis[N],a,b;
bool ok;
void init(){
    s.clear();t.clear();
    ok=false;
    for(int i=0;i<N;i++){
        vis[i]=dis[i]=0;
        edg[i].clear();
    }
}
void spfa()  {
    queue<int>q;
    for(int i=0;i<N;i++)dis[i]=inf;
    dis[1]=0;
    q.push(1);
    vis[1]=1;
    while(!q.empty())  {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<edg[u].size();i++)  {
            int v=edg[u][i];
            if(dis[v]>dis[u]+1)  {
                dis[v]=dis[u]+1;
                if(!vis[v])  {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    printf("%lld\n",min(dis[n]*a,b));
}
void bfs(){
    queue<int>q;
    for(int i=2;i<=n;i++){
        s.insert(i);
    }
    q.push(1);
    dis[1]=0;
    dis[n]=inf;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<edg[u].size();i++){
            int v=edg[u][i];
            if(!s.count(v))continue;
            s.erase(v);t.insert(v);
        }
        for(it = s.begin();it!=s.end();it++){
            q.push(*it);
            dis[*it]=dis[u]+1;
        }
        s.swap(t);
        t.clear();
    }
    printf("%lld\n",min(dis[n]*b,a));
}
int main(){
   int u,v;
   while(~scanf("%d%d%lld%lld",&n,&m,&a,&b)){
    init();
    while(m--){
        scanf("%d%d",&u,&v);
        edg[u].pb(v);
        edg[v].pb(u);
        if(u>v)swap(u,v);
        if(u==1&&v==n)ok=true;
    }
    if(ok)bfs();
    else spfa();
   }
   return 0;
}

 

推荐阅读