//
// main.cpp
// torelax
//
// Created by Rakhman on 11/15/20.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
const long long mxn = 2e6 + 110;
const long long mnn = 1e1 + 1;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
int n, m, k, d[mxn], p[mxn], sz[mxn], ans[mxn];
vector<pair<int, int> > g[mxn];
set<pair<int, int> > st;
bool used[mxn];
set<int> s[mxn];
int get_p(int x){
if(x == p[x]) return x;
else return p[x] = get_p(p[x]);
}
void get(int u, int v){
int U = get_p(u), V = get_p(v);
if(U == V) return ;
if(s[U].size() > s[V].size()){
swap(U, V);
}
p[U] = V;
while(s[U].size() != 0){
int x = *(s[U].begin());
s[U].erase(s[U].begin());
int cnt = s[V].erase(x);
if(cnt > 0){
ans[x] = d[v];
}else{
s[V].insert(x);
}
}
}
int main() {
ios;
cin >> n >> m;
for(int i = 1; i <= n; i++){
d[i] = OO;
p[i] = i;
sz[i] = 1;
}
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
cin >> k;
for(int i = 1; i <= k; i++){
int x;
cin >> x;
d[x] = 0;
st.insert({0, x});
}
while(st.size() != 0){
int x = (st.begin() -> second);
st.erase(st.begin());
for(int i = 0; i < g[x].size(); i++){
int to = g[x][i].F, w = g[x][i].S;
if(d[to] > d[x] + w){
st.erase({d[to], to});
d[to] = d[x] + w;
st.insert({d[to], to});
}
}
}
int q;
cin >> q;
for(int i = 1; i <= q; i++){
int u, v;
cin >> u >> v;
s[u].insert(i);
s[v].insert(i);
}
vector<pair<int, int> > v;
for(int i = 1; i <= n; i++){
v.push_back({d[i], i});
}
sort(v.begin(), v.end());
for(int i = v.size() - 2; i >= 0; i--){
int x = v[i].second;
for(int j = 0; j < g[x].size(); j++){
int to = g[x][j].first;
if(d[to] >= d[x]){
get(to, x);
}
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << nl;
}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < g[x].size(); i++){
| ~~^~~~~~~~~~~~~
plan.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int j = 0; j < g[x].size(); j++){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
141292 KB |
Output is correct |
2 |
Correct |
81 ms |
141420 KB |
Output is correct |
3 |
Correct |
81 ms |
141420 KB |
Output is correct |
4 |
Correct |
90 ms |
141164 KB |
Output is correct |
5 |
Correct |
82 ms |
141548 KB |
Output is correct |
6 |
Correct |
80 ms |
141420 KB |
Output is correct |
7 |
Correct |
86 ms |
141292 KB |
Output is correct |
8 |
Correct |
88 ms |
141280 KB |
Output is correct |
9 |
Correct |
82 ms |
141548 KB |
Output is correct |
10 |
Correct |
83 ms |
141420 KB |
Output is correct |
11 |
Correct |
81 ms |
141440 KB |
Output is correct |
12 |
Correct |
83 ms |
141432 KB |
Output is correct |
13 |
Correct |
84 ms |
141548 KB |
Output is correct |
14 |
Correct |
85 ms |
141420 KB |
Output is correct |
15 |
Correct |
97 ms |
141420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
141292 KB |
Output is correct |
2 |
Correct |
81 ms |
141420 KB |
Output is correct |
3 |
Correct |
81 ms |
141420 KB |
Output is correct |
4 |
Correct |
90 ms |
141164 KB |
Output is correct |
5 |
Correct |
82 ms |
141548 KB |
Output is correct |
6 |
Correct |
80 ms |
141420 KB |
Output is correct |
7 |
Correct |
86 ms |
141292 KB |
Output is correct |
8 |
Correct |
88 ms |
141280 KB |
Output is correct |
9 |
Correct |
82 ms |
141548 KB |
Output is correct |
10 |
Correct |
83 ms |
141420 KB |
Output is correct |
11 |
Correct |
81 ms |
141440 KB |
Output is correct |
12 |
Correct |
83 ms |
141432 KB |
Output is correct |
13 |
Correct |
84 ms |
141548 KB |
Output is correct |
14 |
Correct |
85 ms |
141420 KB |
Output is correct |
15 |
Correct |
97 ms |
141420 KB |
Output is correct |
16 |
Correct |
354 ms |
156772 KB |
Output is correct |
17 |
Correct |
890 ms |
166488 KB |
Output is correct |
18 |
Correct |
121 ms |
143852 KB |
Output is correct |
19 |
Correct |
350 ms |
157540 KB |
Output is correct |
20 |
Correct |
900 ms |
166448 KB |
Output is correct |
21 |
Correct |
596 ms |
159924 KB |
Output is correct |
22 |
Correct |
250 ms |
157280 KB |
Output is correct |
23 |
Correct |
892 ms |
166552 KB |
Output is correct |
24 |
Correct |
991 ms |
166480 KB |
Output is correct |
25 |
Correct |
901 ms |
166420 KB |
Output is correct |
26 |
Correct |
353 ms |
157284 KB |
Output is correct |
27 |
Correct |
406 ms |
157412 KB |
Output is correct |
28 |
Correct |
352 ms |
157420 KB |
Output is correct |
29 |
Correct |
347 ms |
157432 KB |
Output is correct |
30 |
Correct |
354 ms |
157540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
82 ms |
141292 KB |
Output is correct |
2 |
Correct |
79 ms |
141292 KB |
Output is correct |
3 |
Correct |
82 ms |
141292 KB |
Output is correct |
4 |
Correct |
81 ms |
141292 KB |
Output is correct |
5 |
Correct |
80 ms |
141292 KB |
Output is correct |
6 |
Correct |
84 ms |
141420 KB |
Output is correct |
7 |
Correct |
80 ms |
141292 KB |
Output is correct |
8 |
Correct |
81 ms |
141440 KB |
Output is correct |
9 |
Correct |
80 ms |
141292 KB |
Output is correct |
10 |
Correct |
79 ms |
141292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
376 ms |
151844 KB |
Output is correct |
2 |
Correct |
640 ms |
159596 KB |
Output is correct |
3 |
Correct |
688 ms |
159724 KB |
Output is correct |
4 |
Correct |
166 ms |
147172 KB |
Output is correct |
5 |
Correct |
710 ms |
159696 KB |
Output is correct |
6 |
Correct |
666 ms |
159676 KB |
Output is correct |
7 |
Correct |
656 ms |
159624 KB |
Output is correct |
8 |
Correct |
726 ms |
159724 KB |
Output is correct |
9 |
Correct |
700 ms |
159604 KB |
Output is correct |
10 |
Correct |
653 ms |
159604 KB |
Output is correct |
11 |
Correct |
702 ms |
159668 KB |
Output is correct |
12 |
Correct |
639 ms |
159616 KB |
Output is correct |
13 |
Correct |
695 ms |
159724 KB |
Output is correct |
14 |
Correct |
686 ms |
159668 KB |
Output is correct |
15 |
Correct |
649 ms |
159724 KB |
Output is correct |
16 |
Correct |
657 ms |
159660 KB |
Output is correct |
17 |
Correct |
723 ms |
159612 KB |
Output is correct |
18 |
Correct |
714 ms |
159680 KB |
Output is correct |
19 |
Correct |
157 ms |
147116 KB |
Output is correct |
20 |
Correct |
732 ms |
159892 KB |
Output is correct |
21 |
Correct |
549 ms |
160252 KB |
Output is correct |
22 |
Correct |
214 ms |
151464 KB |
Output is correct |
23 |
Correct |
183 ms |
147940 KB |
Output is correct |
24 |
Correct |
220 ms |
151412 KB |
Output is correct |
25 |
Correct |
222 ms |
151924 KB |
Output is correct |
26 |
Correct |
206 ms |
147944 KB |
Output is correct |
27 |
Correct |
164 ms |
147172 KB |
Output is correct |
28 |
Correct |
224 ms |
151520 KB |
Output is correct |
29 |
Correct |
166 ms |
147428 KB |
Output is correct |
30 |
Correct |
210 ms |
151520 KB |
Output is correct |
31 |
Correct |
172 ms |
147556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
88 ms |
141292 KB |
Output is correct |
2 |
Correct |
81 ms |
141420 KB |
Output is correct |
3 |
Correct |
81 ms |
141420 KB |
Output is correct |
4 |
Correct |
90 ms |
141164 KB |
Output is correct |
5 |
Correct |
82 ms |
141548 KB |
Output is correct |
6 |
Correct |
80 ms |
141420 KB |
Output is correct |
7 |
Correct |
86 ms |
141292 KB |
Output is correct |
8 |
Correct |
88 ms |
141280 KB |
Output is correct |
9 |
Correct |
82 ms |
141548 KB |
Output is correct |
10 |
Correct |
83 ms |
141420 KB |
Output is correct |
11 |
Correct |
81 ms |
141440 KB |
Output is correct |
12 |
Correct |
83 ms |
141432 KB |
Output is correct |
13 |
Correct |
84 ms |
141548 KB |
Output is correct |
14 |
Correct |
85 ms |
141420 KB |
Output is correct |
15 |
Correct |
97 ms |
141420 KB |
Output is correct |
16 |
Correct |
354 ms |
156772 KB |
Output is correct |
17 |
Correct |
890 ms |
166488 KB |
Output is correct |
18 |
Correct |
121 ms |
143852 KB |
Output is correct |
19 |
Correct |
350 ms |
157540 KB |
Output is correct |
20 |
Correct |
900 ms |
166448 KB |
Output is correct |
21 |
Correct |
596 ms |
159924 KB |
Output is correct |
22 |
Correct |
250 ms |
157280 KB |
Output is correct |
23 |
Correct |
892 ms |
166552 KB |
Output is correct |
24 |
Correct |
991 ms |
166480 KB |
Output is correct |
25 |
Correct |
901 ms |
166420 KB |
Output is correct |
26 |
Correct |
353 ms |
157284 KB |
Output is correct |
27 |
Correct |
406 ms |
157412 KB |
Output is correct |
28 |
Correct |
352 ms |
157420 KB |
Output is correct |
29 |
Correct |
347 ms |
157432 KB |
Output is correct |
30 |
Correct |
354 ms |
157540 KB |
Output is correct |
31 |
Correct |
82 ms |
141292 KB |
Output is correct |
32 |
Correct |
79 ms |
141292 KB |
Output is correct |
33 |
Correct |
82 ms |
141292 KB |
Output is correct |
34 |
Correct |
81 ms |
141292 KB |
Output is correct |
35 |
Correct |
80 ms |
141292 KB |
Output is correct |
36 |
Correct |
84 ms |
141420 KB |
Output is correct |
37 |
Correct |
80 ms |
141292 KB |
Output is correct |
38 |
Correct |
81 ms |
141440 KB |
Output is correct |
39 |
Correct |
80 ms |
141292 KB |
Output is correct |
40 |
Correct |
79 ms |
141292 KB |
Output is correct |
41 |
Correct |
376 ms |
151844 KB |
Output is correct |
42 |
Correct |
640 ms |
159596 KB |
Output is correct |
43 |
Correct |
688 ms |
159724 KB |
Output is correct |
44 |
Correct |
166 ms |
147172 KB |
Output is correct |
45 |
Correct |
710 ms |
159696 KB |
Output is correct |
46 |
Correct |
666 ms |
159676 KB |
Output is correct |
47 |
Correct |
656 ms |
159624 KB |
Output is correct |
48 |
Correct |
726 ms |
159724 KB |
Output is correct |
49 |
Correct |
700 ms |
159604 KB |
Output is correct |
50 |
Correct |
653 ms |
159604 KB |
Output is correct |
51 |
Correct |
702 ms |
159668 KB |
Output is correct |
52 |
Correct |
639 ms |
159616 KB |
Output is correct |
53 |
Correct |
695 ms |
159724 KB |
Output is correct |
54 |
Correct |
686 ms |
159668 KB |
Output is correct |
55 |
Correct |
649 ms |
159724 KB |
Output is correct |
56 |
Correct |
657 ms |
159660 KB |
Output is correct |
57 |
Correct |
723 ms |
159612 KB |
Output is correct |
58 |
Correct |
714 ms |
159680 KB |
Output is correct |
59 |
Correct |
157 ms |
147116 KB |
Output is correct |
60 |
Correct |
732 ms |
159892 KB |
Output is correct |
61 |
Correct |
549 ms |
160252 KB |
Output is correct |
62 |
Correct |
214 ms |
151464 KB |
Output is correct |
63 |
Correct |
183 ms |
147940 KB |
Output is correct |
64 |
Correct |
220 ms |
151412 KB |
Output is correct |
65 |
Correct |
222 ms |
151924 KB |
Output is correct |
66 |
Correct |
206 ms |
147944 KB |
Output is correct |
67 |
Correct |
164 ms |
147172 KB |
Output is correct |
68 |
Correct |
224 ms |
151520 KB |
Output is correct |
69 |
Correct |
166 ms |
147428 KB |
Output is correct |
70 |
Correct |
210 ms |
151520 KB |
Output is correct |
71 |
Correct |
172 ms |
147556 KB |
Output is correct |
72 |
Correct |
569 ms |
160480 KB |
Output is correct |
73 |
Correct |
933 ms |
171748 KB |
Output is correct |
74 |
Correct |
939 ms |
171964 KB |
Output is correct |
75 |
Correct |
914 ms |
171880 KB |
Output is correct |
76 |
Correct |
936 ms |
171720 KB |
Output is correct |
77 |
Correct |
955 ms |
171844 KB |
Output is correct |
78 |
Correct |
969 ms |
171700 KB |
Output is correct |
79 |
Correct |
909 ms |
171752 KB |
Output is correct |
80 |
Correct |
963 ms |
171676 KB |
Output is correct |
81 |
Correct |
929 ms |
172012 KB |
Output is correct |
82 |
Correct |
915 ms |
171824 KB |
Output is correct |
83 |
Correct |
948 ms |
171716 KB |
Output is correct |
84 |
Correct |
927 ms |
171952 KB |
Output is correct |
85 |
Correct |
978 ms |
171620 KB |
Output is correct |
86 |
Correct |
954 ms |
171828 KB |
Output is correct |
87 |
Correct |
905 ms |
171912 KB |
Output is correct |
88 |
Correct |
909 ms |
171724 KB |
Output is correct |
89 |
Correct |
373 ms |
160152 KB |
Output is correct |
90 |
Correct |
901 ms |
171776 KB |
Output is correct |
91 |
Correct |
866 ms |
171416 KB |
Output is correct |
92 |
Correct |
441 ms |
160356 KB |
Output is correct |
93 |
Correct |
463 ms |
160500 KB |
Output is correct |
94 |
Correct |
443 ms |
160352 KB |
Output is correct |
95 |
Correct |
410 ms |
160356 KB |
Output is correct |
96 |
Correct |
543 ms |
159968 KB |
Output is correct |
97 |
Correct |
428 ms |
159768 KB |
Output is correct |
98 |
Correct |
455 ms |
160364 KB |
Output is correct |
99 |
Correct |
395 ms |
159752 KB |
Output is correct |
100 |
Correct |
446 ms |
160252 KB |
Output is correct |