Submission #1853343

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
#define pb push_back
typedef long long ll;
typedef pair<int,ll> P;
typedef vector<P> vip;

const int MAX_V=200000;
const ll INF=pow(10,17);
int V;
struct edge{int to,cost;};//Dijkstra
vector<edge> G[MAX_V];
bool used[MAX_V];
ll d[MAX_V];
void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+V+1,INF);
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();que.pop();
        int v = p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
void solve(){
    cin>>V;
    int from;
    fol(i,V-1){
        edge t;
        cin >> from>>t.to>>t.cost;
        G[from].pb(t);
        swap(from,t.to);
        G[from].pb(t);
    }
    int q,k;
    cin>>q>>k;
    dijkstra(k);
    int x,y;
    fol(i,q){
        cin>>x>>y;
        cout <<d[x]+d[y]<<endl;
    }
}

int main(){
    solve();
    return 0;
}

Submission Info

Judge Result