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 |
|
|
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 |