Solution for Live Archive 6425 - Intercity

BFS on the gaps.

/*
 * 6425.cpp
 *
 *  Created on: Sep 3, 2014
 *      Author: ghooo
 */

#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <complex>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
//#include <windows.h>

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((ll)v.size())
#define rep(i,m) for(int i=0;i<(int)(m);++i)
#define repe(i,n,m) for(int i=n;i<=(int)(m);++i)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define reset(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define dot(a,b) ((conj(a)*(b)).X)
#define X real()
#define Y imag()
#define length(V) (hypot((V).X,(V).Y))
#define vect(a,b) ((b)-(a))
#define cross(a,b) ((conj(a)*(b)).imag())
#define normalize(v) ((v)/length(v))
#define rotate(p,about,theta) ((p-about)*exp(point(0,theta))+about)
#define pointEqu(a,b) (comp(a.X,b.X)==0 && comp(a.Y,b.Y)==0)
#define clrq(x) while(!x.empty()) x.pop();
#define clrvv(v) rep(i,sz(v))v[i].clear();
#define debug(x) cerr << #x << ": " << x << endl;
#define debugv(v) cerr << #v << ": ";For(it,v)cerr <<(*it)<<", "; cerr<<endl;

typedef stringstream ss;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int> > vii;
typedef long double ld;
typedef complex<double> point;
typedef pair<point, point> segment;
typedef pair<double, point> circle;
typedef vector<point> polygon;
typedef unsigned long long ull;
typedef long long ll;

//==============================================================
// handling triples
typedef pair<ll, pair<ll, ll> > triple;
#define tfirst first
#define tsecond second.first
#define tthird second.second
#define mt(x,y,z) mp(x,mp(y,z))
//---------------------------------------------------------------

const int oo = (int) 1e9;
const double PI = 2 * acos(0.0);
const double eps = 1e-9;

int main() {
 ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif
 int n, k, neww, old;
 while (cin >> n >> k >> neww >> old) {
  vector<vector<int> > adj(n + 1);
  int x, y;
  bool f = false;
  rep(i,k)
  {
   cin >> x >> y;
   adj[x].pb(y);
   adj[y].pb(x);
   if (x == 1 && y == n)
    f = true;
   if (x == n && y == 1)
    f = true;
  }
  for (int i = 1; i <= n; i++)
  {
   sort(all(adj[i]));
   adj[i].pb(n+1);
  }


  if (f) {
   int mn = neww;
   queue<int> q;
   vector<bool> taken(n + 1, false);
   taken[1] = true;
   q.push(1);
   int lvl = 0;
   while (!q.empty()) {
    int s = sz(q);
    while (s--) {
     int cur = q.front();
     q.pop();
     int last = 1;
     for (int i = 0; i < sz(adj[cur]); i++) {
      for(int v = last; v < adj[cur][i]; v++){
       if (taken[v])
        continue;
       taken[v] = true;
       q.push(v);
       if (v == n) {
        mn = min((lvl + 1) * old, mn);
        goto BARRA1;
       }
      }
      last=adj[cur][i]+1;
     }
    }
    if (lvl * old > mn)
     break;
    lvl++;
   }
   BARRA1: ;
   cout << mn << endl;
  } else {
   int mn = old;
   queue<int> q;
   vector<bool> taken(n + 1, false);
   taken[1] = true;
   q.push(1);
   int lvl = 0;
   while (!q.empty()) {
    int s = sz(q);
    while (s--) {
     int cur = q.front();
     q.pop();
     for (int i = 0; i < sz(adj[cur])-1; i++) {
      int v = adj[cur][i];
      if (taken[v])
       continue;
      taken[v] = true;
      q.push(v);
      if (v == n) {
       mn = min((lvl + 1) * neww, mn);
       goto BARRA2;
      }
     }
    }
    lvl++;
    if (lvl * neww > mn)
     break;
   }
   BARRA2: ;
   cout << mn << endl;
  }
 }
 return 0;
}