[USACO 2014 Gold] Roadblock

作法：

考慮從 1 到 n 的最短路，如果擋住的道路不在最短路上，那麼顯然不影響答案（就算其他邊邊權變大了他還是最短路），所以我們只要考慮最短路上的邊。而由題目給的數字範圍知道可以直接枚舉要擋住最短路上的哪條邊。當把一條邊的邊權改為兩倍時，如果新的最短路還有經過這條邊，那麼他一定長的跟舊的最短路一樣，這時可以知道多走的距離就是這條邊的長度。而沒有經過這條邊的話，就把他拔掉做一次最短路即可。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=250+5,maxm=25000+10 ;
 
struct P{int x,y,dis ;};
vector<P> edge ;
bool can[maxm] ;
vector<int> v[maxn] ;
 
struct Q
{
    int id,dis ;
    bool operator < (const Q &rhs) const
    {
        return dis>rhs.dis ;
    }
};
priority_queue<Q> pq ;
bool done[maxn] ;
int n,d[maxn],fa[maxn] ;
int Dijkstra(int st,int ed,int type)
{
    while(!pq.empty()) pq.pop() ;
    fill(d,d+n+1,INF) ; memset(done,0,sizeof(done)) ;
    d[st]=0 ; pq.push((Q){st,0}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(u.id==ed) return d[u.id] ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        for(auto i : v[u.id]) if(can[i])
        {
            int to=edge[i].x==u.id ? edge[i].y : edge[i].x ;
            if(d[to] > d[u.id] + edge[i].dis)
            {
                d[to]=d[u.id]+edge[i].dis ;
                pq.push((Q){to,d[to]}) ;
                if(type) fa[to]=i ;
            }
        }
    }
    return INF ;
}
 
main()
{
    freopen("rblock.in","r",stdin) ;
    freopen("rblock.out","w",stdout) ;
    int m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<m;i++)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        edge.push_back((P){x,y,dis}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
        can[i]=1 ;
    }
 
    int old=Dijkstra(1,n,1) , ans=0 ;
    for(int i=n;i!=1;)
    {
        int x=fa[i] ;
        int from=edge[x].x==i ? edge[x].y : edge[x].x ;
        int val=edge[x].dis ;
        can[x]=0 ; val=min(val,Dijkstra(1,n,0)-old) ;
        ans=max(ans,val) ;
        can[x]=1 ; i=from ;
    }
    printf("%d\n",ans) ;
}