[POI 20 Stage 1] Price List

作法：

以下把長度為 a 的邊簡稱為 a ， b 也一樣。如果起點到終點的只走 a 的最短路為 k * a ，那麼當前最優的兩個解就是 k * a 和 ( k / 2 ) * b + ( k % 2 ) * a ，其中後者的意思是把路上的連續兩個 a 通通都換成 b ，會換出大概一半的 b 。首先是為什麼能換，因為如果A , B , C 是最短路徑上的依序三點，那麼就一定有 AC 之間沒有 a 的邊，否則和最短路矛盾，所以 AC 之間有一條 b 的邊。至於為什麼留下 >= 2 個 a 不換成 b 是比較差的，就有點類似線性規劃的概念，因為最佳解只會出現在邊界，所以要嘛是全取 a ，要嘛是把能換成 b 的通通換成 b 。

但會發現只考慮這樣還不夠，舉個簡單的反例：起點到終點有兩條不相交的路徑，一條長度是 3 * a ，一條長度是 4 * a ，並且 b 相對 a 來說很小。這樣的話沿著 4 * a 的這條路徑把他換成 2 * b 會是最好的選擇，所以我們還必須考慮起點到終點的只經過 b 的路徑。

至於為什麼只要考慮這些情形就好了，其實這也蠻直觀的，就跟上面提到的「最佳解只會出現在邊界」一樣，太多的 a 和 b 混雜在一起總是不會更好。這裡還是給個比較嚴謹的證明：
如果起點到終點的最短路是 ( 2 * k ) a ，那麼我們考慮的只有 2 * k * a 和 k * b ，如果有另外一條路徑的長度是 u * a + v * b ，並且比 2 * k * a 和 k * b 好，那麼就可以列出 u * a + v * b < 2 * k * a 且 u * a + v * b <  k * b，又因為 ( 2 * k ) a 是只走 a 的最短路，所以必須有 u + 2 * v >= 2 * k ，由這幾條式子可以得到 b < 2 * a 且 b > 2 * a ，就得到矛盾了。而如果起點到終點的最短路是 ( 2 * k + 1 ) a ，那麼如果只有考慮 ( 2 * k + 1 ) a 和 a + k * b 的話，一樣可以列出 u * a + v * b < ( 2 * k + 1 ) a 且 u * a + v * b <  a + k * b ，還有 u + 2 * v >= 2 * k + 1 ，去解這三條式子會得到 b < 2 * a 且 u = 0 ，所以只要再多考慮只經過 b 的路徑就可以了。

所以現在問題變成如何找到起點到終點的只經過 b 的最短路。考慮一個樸素的算法：從起點開始BFS，每次BFS時先把所有和當前點 u 相鄰的點標記起來，然後再去枚舉 u 的鄰居的鄰居，如果他和 u 不相鄰那就代表他和 u 之間有一條 b 的邊。但這樣會讓複雜度爛掉（例如一個星狀圖）。接下來我們把上面的作法改進，設 v 是 u 的其中一個鄰居，之後就把他叫作 u 的中繼點，因為 u 要透過他找到一個和 u 不相鄰的點並BFS過去。這時我們會枚舉 v 的鄰居中和 u 不相鄰的點，但如果有一個 v 的鄰居 u2 被 u BFS到了（也就是他和 u 不相鄰），那麼之後就不會有任何一個 v 的鄰居能夠以 v 為中繼點去BFS到 u2 了。因為從 queue 裡取出的點和起點的最短路長度是遞增的，所以就算之後還有一個點可以以 v 為中繼點去更新到 u2 ，他也不會更好。所以我們只要對每個點 v 維護一個 vector ，代表「以 v 為中繼點時還需要考慮的點們」，每次枚舉到 u 的鄰居 v 的時候就只要考慮這些點就好了，並且在作完 v 時把所有和 u 相鄰的點留在 vector 裡，因為和 u 不相鄰的之後就不需考慮了。

這樣就會過了，但複雜度不太好估。考慮每個點被當中繼點的時候他的鄰居們到底會被枚舉幾次，記 a_1 , a_2 , ... , a_k 是 v 的所有鄰居，並且是按照這些順序從 queue 裡面拿出來的。記集合 A_i 代表 a_i 的鄰居和 v 的鄰居的交集，那麼在 v 當中繼點時，他的鄰居們被枚舉到的次數就是：
k + | A_1 | + | A_1 ∩ A_2 | + | A_1 ∩ A_2 ∩ A_3 | + ... <=  k + | A_1 | + | A_2 | + | A_3 | + ... + | A_k |
因為對每個點來說， k 就是那個點的度，所以把每個點的上面那條式子的值加起來後 k 的總和就是O（M）。至於後面那坨東西，我們考慮以 v 為其中一個頂點的三角形們，就會得到 | A_1 | + | A_2 | + | A_3 | + ... + | A_k |  <= 2 * 三角形的數量，因為如果 a_j ∈ A_i ，那麼 v , a_i , a_j 就形成了一個三角形。所以我們的總複雜度就是O（圖中的三角形數量），而這個東西的複雜度是O（M * sqrt(M)），證明就在這邊略去，詳細可以參考這個網站。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 100000000
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn],v2[maxn],tmp ;
int d1[maxn],d2[maxn] ;
queue<int> q ;
int type[maxn] ;
main()
{
    int n,m,st ;
    LL a,b ; scanf("%d%d%d%lld%lld",&n,&m,&st,&a,&b) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
        v2[x].push_back(y) ;
        v2[y].push_back(x) ;
    }
 
    fill(d1,d1+n+1,INF) ;
    d1[st]=0 ; q.push(st) ;
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ;
        for(int i=0;i<v[u].size();i++) if(d1[v[u][i]]==INF)
        {
            d1[v[u][i]]=d1[u]+1 ;
            q.push(v[u][i]) ;
        }
    }
 
    fill(d2,d2+n+1,INF) ;
    d2[st]=0 ; q.push(st) ;
    int cnt=0 ;
    while(!q.empty())
    {
        int u=q.front() ; q.pop() ; cnt++ ;
        for(int i=0;i<v[u].size();i++) type[v[u][i]]=cnt ;
        for(int i=0;i<v[u].size();i++)
        {
            tmp.clear() ;
            int u2=v[u][i] ;
            for(int j=0;j<v2[u2].size();j++)
            {
                if(v2[u2][j]==u) continue ;
                if(type[v2[u2][j]]==cnt) tmp.push_back(v2[u2][j]) ;
                else if(d2[v2[u2][j]]==INF)
                    d2[v2[u2][j]]=d2[u]+1 , q.push(v2[u2][j]) ;
            }
            v2[u2]=tmp ;
        }
    }
    for(int i=1;i<=n;i++)
    {
        LL ans=min(a*d1[i], b*(d1[i]/2) + (d1[i]%2)*a) ;
        ans=min(ans,b*d2[i]) ;
        printf("%lld\n",ans) ;
    }
}