[TIOJ]1996. 傳送門

題目連結：http://tioj.ck.tp.edu.tw/problems/1996

求最短路徑的題目，邊權只有0,8,16這三種。
當邊權為0時可以直接將兩點合併成一點，當邊權為8就建起一條邊，當邊權為16就開一個新的點變成連兩次邊權8。
因為邊權都只剩8，所以BFS找最短路即可。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include "lib1996.h"
#define lld long long
#define PB push_back
#define INF 2147483647
#define N 6000005
using namespace std;
typedef pair<int,int> Pair;
struct DJS{
    int p[N];
    void Init(){for(int i = 0 ; i < N ; i++)p[i] = i;}
    inline int query(int x){return p[x] == x ? x : p[x] = query(p[x]);}
    void unite(int x,int y){
        x = query(x);y = query(y);
        p[x] = y;
    }
}djs;
int dis[N];
vector<int> v[N];
void init(int n,int m,int A[],int B[],int K[]){
    djs.Init();
    fill(dis,dis+N,INF);
    int t = n+1;
    for(int i = 0 ; i < m ; i++)if(!K[i])djs.unite(A[i],B[i]);
    for(int i = 0 ; i < m ; i++){
        A[i] = djs.query(A[i]);
        B[i] = djs.query(B[i]);
        if(K[i] == 1 && A[i] != B[i])v[A[i]].PB(B[i]),v[B[i]].PB(A[i]);
        else if(K[i] == 2 && A[i] != B[i]){
            v[A[i]].PB(t);v[t].PB(A[i]);
            v[B[i]].PB(t);v[t].PB(B[i]);
            ++t;
        }
    }
    queue<int> q;
    q.push(djs.query(0));
    dis[djs.query(0)] = 0;
    while(!q.empty()){
        int now = q.front();q.pop();
        for(int i : v[now]){
            if(dis[i] != INF)continue;
            dis[i] = dis[now]+8;
            q.push(i);
        }
    }
}
inline int get_cost(int x){
    return dis[djs.query(x)] == INF ? -1 : dis[djs.query(x)]*2; 
}