ABC 070 D Transit Tree Pass

問題

見た感じ

与えられているのは木なので、kから各ノードへの最短距離を計算すれば終わりそう.

解法

ダイクストラ法でkから各ノードへの最短距離を計算した。
そして、クエリに合わせて、足し算した。

ソースコード

const int N_MAX=100001;
vector<edge> v[N_MAX];
int n,k,Q;
pint q[N_MAX];
ll d[N_MAX];//ll=long long

void dijkstra(int s){
    fill(d,d+n,INF18);
    queue<int> que;
    que.push(s);
    d[s]=0;
    while(!que.empty()){
        int w=que.front();
        que.pop();
        rep(i,v[w].size()){
            if(d[v[w][i].to]>d[w]+v[w][i].cost){
                d[v[w][i].to]=d[w]+v[w][i].cost;
                que.push(v[w][i].to);
            }
        }
    }
    return;
}

int main(){
    int i,x,y,c;
    //入力
    cin>>n;
    rep(i,n-1){
        cin>>x>>y>>c;
        v[x-1].push_back(edge(y-1,c));
        v[y-1].push_back(edge(x-1,c));
    }
    cin>>Q>>k;
    rep(i,Q){
        cin>>x>>y;
        q[i].first=x-1;
        q[i].second=y-1;
    }
    //処理
    dijkstra(k-1);
    //出力
    rep(i,Q){
        cout<<d[q[i].first]+d[q[i].second]<<endl;
    }
}