Submission #3027492

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)

typedef pair<int, int> P;

const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

template<class T>
bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T>
bool chmin(T &a, const T &b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

#define MAX_V 100000

struct edge {
	int to;
	ll cost;
};

int V;
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(int s) {
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + V, 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;
		REP(i, G[v].size()) {
			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));
			}
		}
	}
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> V;
	REP(i, V - 1) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		a--, b--;
		edge e;
		e.to = b, e.cost = c;
		G[a].push_back(e);
		e.to = a, e.cost = c;
		G[b].push_back(e);
	}
	
	int q, k;
	cin >> q >> k;
	k--;
	
	dijkstra(k);
	
	REP(i, q) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		cout << d[x] + d[y] << endl;
	}
	
	
	return 0;
}

Submission Info

Judge Result