Submission #3027499


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--;
	int x[q], y[q];
	REP(i, q) {
		int xin, yin;
		cin >> xin >> yin;
		xin--, yin--;
		x[i] = xin, y[i] = yin;
	}
	
	dijkstra(k);
	
	
	REP(i, q) {
		cout << d[x[i]] + d[y[i]] << endl;
	}
	
	
	return 0;
}

Submission Info

Submission Time
Task D - Transit Tree Path
User sdub
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1720 Byte
Status WA
Exec Time 216 ms
Memory 10736 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
WA × 1
AC × 4
WA × 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
sample_03.txt WA 2 ms 2560 KB
subtask_1_1.txt WA 2 ms 2560 KB
subtask_1_10.txt AC 111 ms 3840 KB
subtask_1_11.txt WA 3 ms 2688 KB
subtask_1_12.txt WA 11 ms 2688 KB
subtask_1_13.txt WA 36 ms 2944 KB
subtask_1_14.txt WA 2 ms 2560 KB
subtask_1_15.txt WA 4 ms 2944 KB
subtask_1_16.txt WA 212 ms 10624 KB
subtask_1_17.txt WA 212 ms 10624 KB
subtask_1_18.txt WA 216 ms 10624 KB
subtask_1_19.txt WA 215 ms 10624 KB
subtask_1_2.txt WA 3 ms 2688 KB
subtask_1_20.txt WA 204 ms 9984 KB
subtask_1_21.txt WA 206 ms 9984 KB
subtask_1_22.txt WA 206 ms 9984 KB
subtask_1_23.txt WA 203 ms 9984 KB
subtask_1_24.txt AC 216 ms 10608 KB
subtask_1_25.txt WA 201 ms 10736 KB
subtask_1_26.txt WA 202 ms 10736 KB
subtask_1_27.txt WA 215 ms 10480 KB
subtask_1_28.txt WA 200 ms 9984 KB
subtask_1_3.txt WA 119 ms 8192 KB
subtask_1_4.txt WA 2 ms 2560 KB
subtask_1_5.txt WA 145 ms 4224 KB
subtask_1_6.txt WA 22 ms 3328 KB
subtask_1_7.txt WA 121 ms 3968 KB
subtask_1_8.txt WA 2 ms 2560 KB
subtask_1_9.txt WA 81 ms 8960 KB