[TIOJ 1689][USACO 2009 Gold] 安全路徑 Safe Travel

作法：

這題是我去查解才會的，做法和這個網站一樣。
總之就是先建出最短路徑樹，那麼對每個點來說走到他但不能經過的邊就是他連他老爸的邊，所以對每個點 u ，答案的走法一定會長的像「先從根走到一個點 v (路上不能經過 u )」，然後跳到 u 的子樹( 含 u )，然後再往上沿樹邊走到 u ( 或如果跳到 u 就不走 )，這件事可以由「因為他是最短路徑樹」直接得到。所以和那個網站講的一樣，對每個節點 u 維護一個 priority queue ，裡面放的值是 ( x , val ) ，其中 x 是 u 的一個子節點，且 x 可沿著非樹邊走到 v ， val 就存 dist[ x ] + dist[ v ] + dis[ x ][ v ] ，其中 dist 代表每個點到根的最短距離，這樣我需要的值就是 priority queue 裡面的 val 最小的數，再減掉 dist[ u ] 就可以了。合併的部分我是用啟發式合併，左偏樹聽起來太恐怖了。

另外，如果 priority queue 的 top ，假設叫 ( x , val ) 好了，那麼如果 x 是當前節點 u 的子孫，那這條邊就是不合法的，必須要 pop 掉，一直 pop 到可以用的邊就好了。並且如果一條邊在我們做到節點 u 的時候他就被 pop 掉了，那麼在做 u 的祖先的時候，這條邊對 u 的祖先們一定也是不合法的邊( 因為從根走到 x 會經過 u ，這就代表了會經過 u 的每個祖先 )。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=100000+10 ;
struct P{int to,dis;};
struct Q
{
    int id,dis ;
    bool operator < (const Q &rhs) const
    {
        return dis>rhs.dis ;
    }
};
 
vector<P> v[maxn] ;
vector<int> v2[maxn] ;
int fa[maxn] ;
int n,d[maxn] ;
bool done[maxn] ;
priority_queue<Q> pq ;
 
void Dijkstra(int st)
{
    fill(d+1,d+n+1,INF) ;
    d[st]=0 ; pq.push((Q){st,0}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        if(u.id!=st) v2[fa[u.id]].push_back(u.id) ;
        for(auto i : v[u.id]) if(d[i.to] > d[u.id]+i.dis)
        {
            fa[i.to]=u.id ;
            d[i.to]=d[u.id]+i.dis ;
            pq.push((Q){i.to,d[i.to]}) ;
        }
    }
}
 
int in[maxn],out[maxn],t=0 ;
void dfs0(int x)
{
    in[x]=++t ;
    for(auto i : v2[x]) dfs0(i) ;
    out[x]=++t ;
}
 
bool is_fa(int x,int y) /** x is fa of y , x = y -> return true */
{
    return in[x]<=in[y] && out[x]>=out[y] ;
}
 
int ans[maxn] ;
priority_queue<Q> pq2[maxn] ;
int id[maxn] ;
 
int merge(int x,int y)
{
    if(pq2[x].size()<pq2[y].size()) swap(x,y) ;
    while(!pq2[y].empty())
        pq2[x].push(pq2[y].top()) , pq2[y].pop() ;
    return x ;
}
 
void dfs1(int x)
{
    id[x]=x ;
    for(auto i : v2[x]) dfs1(i) , id[x]=merge(id[x],id[i]) ;
    for(auto i : v[x]) if(i.to!=fa[x])
        pq2[id[x]].push((Q){i.to,d[i.to]+d[x]+i.dis}) ;
    while(!pq2[id[x]].empty() && is_fa(x,pq2[id[x]].top().id)) pq2[id[x]].pop() ;
    ans[x]= pq2[id[x]].empty() ? -1 : (pq2[id[x]].top().dis - d[x]) ;
}
 
main()
{
    int m ; scanf("%d%d",&n,&m) ;
    while(m--)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
        v[y].push_back((P){x,dis}) ;
    }
    Dijkstra(1) ;
    dfs0(1) ;
    dfs1(1) ;
    for(int i=2;i<=n;i++) printf("%d\n",ans[i]) ;
}