JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge
先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, v ) )と ( v, lca( u, v ) )で辿る全ての辺の中の最小値だと分かる。
実装は、今の僕には重い。。。でもいい練習になった。前からずっと勘違いしてたのがDijkstraやbellman-fordは Single Source Shortest Pathしかできないと思っていたことだ。しかし、今回はDijikstraでMultiple Source やってみて同じO( E lg V )ができると悟った、始点を増やすことだけだった。
ちょっと間抜けしてできたバグは：
１。priority_queue< pii > 宣言して最短距離を計算しようとした、TLE。
２。mincost[ i ][ u ] = mincost[ i - 1 ][ u ], mincost[ i - 1 ][ mid ];　こんなことした。。。
全体的になんか
UVA 11354 Bond ( 最小瓶頸路徑 Kruskal + LCA ) - 0w1これと似てる様な感じがする。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXQ = 1e5 + 5;
const int MAXL = 1e3 + 3;
const int INF = 0x3f3f3f3f;
const int LGN = 20 + 1;

void upmin(int &x, int v){ if( x > v ) x = v; }

int n, m, k, q;

struct Edge{
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0): u(_u), v(_v), w(_w){}
    bool operator < (const Edge &oth) const{ return w > oth.w; }
} es[ MAXM * 2 ];

vector<int> G[ MAXN ];
vector<int> festival;

typedef pair<int, int> pii;
struct Dijkstra{
    int vis[ MAXN ], dis[ MAXN ];
    void init(){
        // memset( vis, 0, sizeof(vis) );
        memset( dis, INF, sizeof(dis) );
    }
    void solve(){
        priority_queue< pii, vector<pii>, greater<pii> > pq;
        for(int i = 0; i < festival.size(); ++i) //
            pq.push( pii( dis[ festival[ i ] ] = 0, festival[ i ] ) );
        while( !pq.empty() ){
            int u = pq.top().second;
            pq.pop();
            for(int vidx: G[ u ]){
                Edge &e = es[ vidx ];
                if( dis[ e.v ] > dis[ u ] + e.w ){
                    dis[ e.v ] = dis[ u ] + e.w;
                    pq.push( pii( dis[ e.v ], e.v ) );
                }
            }
        }
    }
} dijkstra;

struct UnionFind{
    int fa[ MAXN ];
    void init(){
        for(int i = 0; i < MAXN; ++i)
            fa[ i ] = i;
    }
    int find(int a){ return fa[ a ] == a ? a : fa[ a ] = find( fa[ a ] ); }
    bool unite(int a, int b){
        int x = find( a );
        int y = find( b );
        if( x == y ) return false;
        fa[ x ] = y; return true;
    }
} uf;

vector<Edge> MST[ MAXN ];
int cost[ MAXN ];
struct Kruskal{
    vector<Edge> chose;
    void init(){
        chose.clear();
        uf.init();
    }
    void solve(){
        vector<Edge> cand;
        for(int i = 0; i < m; ++i){
            Edge &e = es[ i ];
            cand.push_back( Edge( e.u, e.v, min( cost[ e.u ], cost[ e.v ] ) ) );
        }
        sort( cand.begin(), cand.end() );
        for(int i = 0; i < m; ++i){
            if( uf.unite( cand[ i ].u, cand[ i ].v ) ){
                chose.push_back( cand[ i ] );
                MST[ cand[ i ].u ].push_back( cand[ i ] );
                MST[ cand[ i ].v ].push_back( Edge( cand[ i ].v, cand[ i ].u, cand[ i ].w ) );
                if( chose.size() == n - 1 ) break;
            }
        }
        // for(int i = 0; i < chose.size(); ++i)
            // printf("*chose[ %d ] : %d < - > %d = %d\n", i, chose[i].u, chose[i].v, chose[i].w);
        assert( chose.size() == n - 1 );
    }
} kruskal;

struct LCA{
    int anc[ LGN ][ MAXN ];
    int mincost[ LGN ][ MAXN ], depth[ MAXN ];
    void init(){
        memset( anc, -1, sizeof(anc) );
        memset( mincost, INF, sizeof(mincost) );
    }
    void dfs(int u, int fa, int dpt){
        depth[ u ] = dpt;
        for(Edge &e: MST[ u ]){
            if( e.v == fa ) continue;
            // printf("anc[ %d ] : %d\n", e.v, u);
            anc[ 0 ][ e.v ] = u;
            mincost[ 0 ][ e.v ] = e.w;
            // printf("mincost[ %d ] : %d\n", e.v, e.w);
            dfs( e.v, u, dpt + 1 );
        }
    }
    void preLCA(){
        for(int i = 1; i < LGN; ++i)
            for(int u = 1; u <= n; ++u)
                if( anc[ i - 1 ][ u ] != -1 ){
                    int mid = anc[ i - 1 ][ u ];
                    anc[ i ][ u ] = anc[ i - 1 ][ mid ];
                    if( anc[ i ][ u ] == -1 ) continue;
                    // mincost[ i ][ u ] = mincost[ i - 1 ][ u ], mincost[ i - 1 ][ mid ]; = = WT
                    mincost[ i ][ u ] = min( mincost[ i - 1 ][ u ], mincost[ i - 1 ][ mid ] );
                }
    }
    void preprocess(){
        dfs( 1, -1, 0 );
        preLCA();
    }
    int qMincost(int u, int v){
        int res = INF;
        if( depth[ u ] < depth[ v ] ) swap( u, v );
        int diff = depth[ u ] - depth[ v ];
        for(int i = LGN - 1; i >= 0; --i){
            if( diff - ( 1 << i ) >= 0 ){
                diff -= ( 1 << i );
                upmin( res, mincost[ i ][ u ] );
                u = anc[ i ][ u ];
            }
        }
        if( u == v ) return res;
        for(int i = LGN - 1; i >= 0; --i)
            if( anc[ i ][ u ] != anc[ i ][ v ] ){
                upmin( res, mincost[ i ][ u ] );
                upmin( res, mincost[ i ][ v ] );
                u = anc[ i ][ u ];
                v = anc[ i ][ v ];
            }
        upmin( res, mincost[ 0 ][ u ] );
        upmin( res, mincost[ 0 ][ v ] );
        return res;
    }
} lca;

void preSolve(){
    dijkstra.init();
    dijkstra.solve();
    for(int i = 1; i <= n; ++i)
        cost[ i ] = dijkstra.dis[ i ];
    kruskal.init();
    kruskal.solve();
    lca.init();
    lca.preprocess();
}

int main(){
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(int i = 0; i < m; ++i){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        es[ i ] = Edge( u, v, w );
        es[ m + i ] = Edge( v, u, w );
        G[ u ].push_back( i );
        G[ v ].push_back( m + i );
    }
    for(int i = 0; i < k; ++i){
        int p; scanf("%d", &p);
        festival.push_back( p );
    }
    preSolve();
    while( q-- ){
        int u, v; scanf("%d%d", &u, &v);
        printf("%d\n", lca.qMincost( u, v ));
    }
    return 0;
}