[SCU4444] Travel [2015 Sichuan Province Contest Final I]

題意

有 n 點，n⋅(n−1)2條邊，一些邊權值為 a ，一些邊權值為b， n≤105 , a 邊個數≤5⋅105，求 1→n 最短路

題解

若 a 連接配接1→n，且 a≤b ，則答案為 a

若b連接配接 1→n ，且 b≤a ，則答案為 b

若b連接配接 1→n ，而 a<b ，則求隻有 a 的最短路，再判斷。

若a連接配接 1→n ，而 a>b ，則 bfs ，将未通路的點入集合，每到一個點，枚舉未通路的點是否能被通路到，可通路到則将其放入下一層的 bfs ，直到找到 n 。因為每一個點隻會被通路一次，而且a邊相對于 b <script id="MathJax-Element-1224" type="math/tex">b</script>邊來說很少，實際跑起來很快。

代碼

/****************************************\
* Author : ztx
* Title  : I - Travel
* ALG    :
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
typedef double lf ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG =  ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
    while (ret=getchar() , ret<'!') ;
    while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
    ret[]=;while (CH=getchar() , CH<'!') ;
    while (ret[++ret[]]=CH,CH=getchar(),CH>'!') ;
    ret[ret[]+]=;
}

#include <cstring>
#include <deque>
#include <set>

#define  maxn  100010LL
#define  maxm  500010LL
#define  infi  1000000010LL

struct FST { int to,next; } e[maxm<<] ;
int star[maxn] , tote ;
inline void AddEdge(int u,int v) {
    e[++tote].to = v; e[tote].next = star[u]; star[u] = tote;
    e[++tote].to = u; e[tote].next = star[v]; star[v] = tote;
}

int n , m , a , b ;
std::deque<int>q ;
std::set<int>vis,left ;
std::set<int>:: iterator it ;
ll ans ;
int dis[maxn] ;
bool inq[maxn] ;

inline void all_init() {
    memset(star,,sizeof star) ;
    tote =  ;
}

inline void bfs() {
int u , v , p ;
    if (b >= a) {
        ans = a ; return ;
    }
    vis.clear() , left.clear() , q.clear() ;
    Rep (u,,n) vis.insert(u) ;
    dis[] =  , dis[n] = infi ;
    q.push_back() ;
    while (!q.empty()) {
        u = q.front() , q.pop_front() ;
        for (p=star[u];p;p=e[p].next)
            if (v=e[p].to,it=vis.lower_bound(v),it!=vis.end()&&v==*it)
                vis.erase(it),left.insert(v) ;
        for (it=vis.begin();it!=vis.end();it++)
            q.push_back(*it) , dis[*it] = dis[u]+ ;
        if (dis[n] != infi) {
            ans = (ll)dis[n]*(ll)b ;
            if (ans > a) ans = a ;
            return ;
        }
        vis.swap(left) ;
        left.clear() ;
    }
    ans = a ;
}

inline void spfa() {
int u , v , p ;
    if (a >= b) {
        ans = b ; return ;
    }
    q.clear() ;
    Rep (u,,n) dis[u] = infi , inq[u] = false ;
    dis[] =  ; q.push_back() ;
    while (!q.empty())
        for (u=q.front(),q.pop_front(),inq[u]=false,p=star[u];p;p=e[p].next)
            if (v=e[p].to,dis[v]>dis[u]+)  // 爆int
                if (dis[v]=dis[u]+,!inq[v])
                    if (inq[v]=true,!q.empty()&&dis[v]<=dis[q.front()]) q.push_front(v) ;
                    else q.push_back(v) ;
    if (dis[n] == infi) ans = b ; 
    else if (ans=(ll)dis[n]*(ll)a,ans > b) ans = b ;
}

int main() {
int i , u , v , is_a ;
//    #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    while (scanf("%d%d%d%d", &n, &m, &a, &b) != EOF) {
        all_init() ;
        is_a = false ;
        rep (i,,m) {
            read(u) , read(v) ;
            AddEdge(u,v) ;
            if ((u==&&v==n) || (u==n&&v==)) is_a = true ;
        }
        if (is_a) bfs() ;
        else spfa() ;
        printf("%lld\n", ans) ;
    }
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return  ;
}