Submission #1507792


Source Code Expand

Copy
// #include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <fstream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
// #include <unordered_map>
#include <set>
#include <utility>
#include <bitset>
#include <limits>
#include <climits>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())


const ll INF = 1000000000000000000LL;// 1e18


template <typename T>
void dij1(int nV, vector<vector<pair<int,T>>>& adjacent, vector<T>& d, int start) {
	// nV: |V|
	d.assign(nV, INF);
	d[start] = 0;
	vector<int> prev(nV, -1);

	priority_queue<pair<T, int>> Q;
	Q.push(make_pair(0, start));

	vector<bool> visited(nV, false);

	while (!Q.empty()) {
		T du = -Q.top().first;
        int u = Q.top().second; Q.pop();
		if (visited[u]) continue;
		visited[u] = true;

		int c = adjacent[u].size();
		for (int i=0; i<c; ++i) {
			int v = adjacent[u][i].first;
			T distance = adjacent[u][i].second;
			T alt = du + distance;
			if (d[v] > alt) {
				d[v] = alt;
				prev[v] = u;
				Q.push(make_pair(-alt, v));
			}
		}
	}
}

int main() {
    int N; cin >> N;

    vector<vector<pair<int,ll>>> adj(N);
    rep(i, N-1) {
        int ai,bi; ll ci; cin >> ai >> bi >> ci;
        --ai; --bi;
        adj[ai].pb(make_pair(bi, ci));
        adj[bi].pb(make_pair(ai, ci));
    }
    int Q, K; cin >> Q >> K;
    --K;

    vector<ll> d(N, INF);
    dij1(N, adj, d, K);
    // cout << d << endl;

    rep(j, Q) {
        int xi,yi; cin >> xi >> yi;
        --xi; --yi;
        ll ans = d[xi] + d[yi];
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Transit Tree Path
User naoya_t
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2661 Byte
Status
Exec Time 343 ms
Memory 11504 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 400 / 400 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 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_1.txt 1 ms 256 KB
subtask_1_10.txt 129 ms 1024 KB
subtask_1_11.txt 2 ms 256 KB
subtask_1_12.txt 12 ms 256 KB
subtask_1_13.txt 42 ms 512 KB
subtask_1_14.txt 1 ms 256 KB
subtask_1_15.txt 7 ms 768 KB
subtask_1_16.txt 341 ms 9976 KB
subtask_1_17.txt 342 ms 9976 KB
subtask_1_18.txt 343 ms 9976 KB
subtask_1_19.txt 343 ms 9976 KB
subtask_1_2.txt 3 ms 384 KB
subtask_1_20.txt 329 ms 9592 KB
subtask_1_21.txt 327 ms 9464 KB
subtask_1_22.txt 325 ms 9592 KB
subtask_1_23.txt 336 ms 9592 KB
subtask_1_24.txt 338 ms 11504 KB
subtask_1_25.txt 329 ms 11504 KB
subtask_1_26.txt 331 ms 11504 KB
subtask_1_27.txt 332 ms 11504 KB
subtask_1_28.txt 305 ms 9592 KB
subtask_1_3.txt 205 ms 7380 KB
subtask_1_4.txt 1 ms 256 KB
subtask_1_5.txt 181 ms 1280 KB
subtask_1_6.txt 32 ms 1152 KB
subtask_1_7.txt 149 ms 1152 KB
subtask_1_8.txt 1 ms 256 KB
subtask_1_9.txt 172 ms 8960 KB