#include <bits/stdc++.h>
using namespace std;
int dist[100005], par[100005], ans[100005];
vector<pair<int, int> > adj[100005];
priority_queue<pair<int, int> > pq;
vector<pair<int, int> > edge;
set<int> s[100005];
bool cmp(pair<int, int> x, pair<int, int> y)
{
return (min(dist[x.first], dist[x.second])>min(dist[y.first], dist[y.second]));
}
int findPar(int u)
{
if (par[u]==u)
return u;
par[u]=findPar(par[u]);
return par[u];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, p, q;
cin >> n >> m;
for (int i=1; i<=m; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
edge.push_back({u, v});
}
cin >> p;
for (int i=1; i<=n; i++)
dist[i]=1e9;
for (int i=1; i<=p; i++)
{
int u;
cin >> u;
dist[u]=0;
pq.push({0, u});
}
while (!pq.empty())
{
int num=-pq.top().first, u=pq.top().second;
pq.pop();
if (dist[u]<num)
continue;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first, w=adj[u][i].second;
if (dist[v]>dist[u]+w)
{
dist[v]=dist[u]+w;
pq.push({-dist[v], v});
}
}
}
sort(edge.begin(), edge.end(), cmp);
cin >> q;
for (int i=1; i<=q; i++)
{
int u, v;
cin >> u >> v;
s[u].insert(i);
s[v].insert(i);
}
for (int i=1; i<=n; i++)
par[i]=i;
for (int i=0; i<edge.size(); i++)
{
int u=edge[i].first, v=edge[i].second;
int paru=findPar(u), parv=findPar(v), num=min(dist[u], dist[v]);
if (paru==parv)
continue;
if (s[paru].size()>s[parv].size())
swap(paru, parv);
for (int x:s[paru])
{
if (s[parv].count(x))
{
ans[x]=num;
s[parv].erase(x);
}
else
s[parv].insert(x);
}
par[paru]=parv;
}
for (int i=1; i<=q; i++)
cout << ans[i] << '\n';
return 0;
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i=0; i<adj[u].size(); i++)
| ~^~~~~~~~~~~~~~
plan.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i=0; i<edge.size(); i++)
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
6 ms |
7640 KB |
Output is correct |
3 |
Correct |
7 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7572 KB |
Output is correct |
6 |
Correct |
5 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
5 ms |
7380 KB |
Output is correct |
9 |
Correct |
5 ms |
7516 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7508 KB |
Output is correct |
12 |
Correct |
5 ms |
7564 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
6 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
6 ms |
7640 KB |
Output is correct |
3 |
Correct |
7 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7572 KB |
Output is correct |
6 |
Correct |
5 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
5 ms |
7380 KB |
Output is correct |
9 |
Correct |
5 ms |
7516 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7508 KB |
Output is correct |
12 |
Correct |
5 ms |
7564 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
6 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7508 KB |
Output is correct |
16 |
Correct |
267 ms |
26176 KB |
Output is correct |
17 |
Correct |
618 ms |
48120 KB |
Output is correct |
18 |
Correct |
36 ms |
10960 KB |
Output is correct |
19 |
Correct |
187 ms |
26644 KB |
Output is correct |
20 |
Correct |
570 ms |
48300 KB |
Output is correct |
21 |
Correct |
328 ms |
34504 KB |
Output is correct |
22 |
Correct |
162 ms |
25528 KB |
Output is correct |
23 |
Correct |
549 ms |
48256 KB |
Output is correct |
24 |
Correct |
573 ms |
48144 KB |
Output is correct |
25 |
Correct |
538 ms |
48176 KB |
Output is correct |
26 |
Correct |
189 ms |
26416 KB |
Output is correct |
27 |
Correct |
180 ms |
26524 KB |
Output is correct |
28 |
Correct |
178 ms |
26436 KB |
Output is correct |
29 |
Correct |
184 ms |
26508 KB |
Output is correct |
30 |
Correct |
180 ms |
26672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
4 ms |
7304 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7380 KB |
Output is correct |
6 |
Correct |
4 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
3 ms |
7380 KB |
Output is correct |
9 |
Correct |
4 ms |
7380 KB |
Output is correct |
10 |
Correct |
3 ms |
7380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
17132 KB |
Output is correct |
2 |
Correct |
386 ms |
28032 KB |
Output is correct |
3 |
Correct |
370 ms |
28184 KB |
Output is correct |
4 |
Correct |
67 ms |
12056 KB |
Output is correct |
5 |
Correct |
346 ms |
28084 KB |
Output is correct |
6 |
Correct |
364 ms |
28080 KB |
Output is correct |
7 |
Correct |
364 ms |
28008 KB |
Output is correct |
8 |
Correct |
368 ms |
28068 KB |
Output is correct |
9 |
Correct |
364 ms |
28024 KB |
Output is correct |
10 |
Correct |
351 ms |
28080 KB |
Output is correct |
11 |
Correct |
343 ms |
28104 KB |
Output is correct |
12 |
Correct |
355 ms |
28344 KB |
Output is correct |
13 |
Correct |
346 ms |
28092 KB |
Output is correct |
14 |
Correct |
365 ms |
28076 KB |
Output is correct |
15 |
Correct |
354 ms |
29172 KB |
Output is correct |
16 |
Correct |
350 ms |
28092 KB |
Output is correct |
17 |
Correct |
363 ms |
28100 KB |
Output is correct |
18 |
Correct |
408 ms |
28144 KB |
Output is correct |
19 |
Correct |
52 ms |
12064 KB |
Output is correct |
20 |
Correct |
387 ms |
28100 KB |
Output is correct |
21 |
Correct |
326 ms |
27732 KB |
Output is correct |
22 |
Correct |
67 ms |
13988 KB |
Output is correct |
23 |
Correct |
66 ms |
12576 KB |
Output is correct |
24 |
Correct |
65 ms |
13892 KB |
Output is correct |
25 |
Correct |
62 ms |
13960 KB |
Output is correct |
26 |
Correct |
78 ms |
12728 KB |
Output is correct |
27 |
Correct |
67 ms |
12064 KB |
Output is correct |
28 |
Correct |
70 ms |
13884 KB |
Output is correct |
29 |
Correct |
67 ms |
11956 KB |
Output is correct |
30 |
Correct |
64 ms |
14008 KB |
Output is correct |
31 |
Correct |
67 ms |
12028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
6 ms |
7640 KB |
Output is correct |
3 |
Correct |
7 ms |
7508 KB |
Output is correct |
4 |
Correct |
4 ms |
7380 KB |
Output is correct |
5 |
Correct |
5 ms |
7572 KB |
Output is correct |
6 |
Correct |
5 ms |
7508 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
5 ms |
7380 KB |
Output is correct |
9 |
Correct |
5 ms |
7516 KB |
Output is correct |
10 |
Correct |
5 ms |
7508 KB |
Output is correct |
11 |
Correct |
5 ms |
7508 KB |
Output is correct |
12 |
Correct |
5 ms |
7564 KB |
Output is correct |
13 |
Correct |
5 ms |
7508 KB |
Output is correct |
14 |
Correct |
6 ms |
7508 KB |
Output is correct |
15 |
Correct |
5 ms |
7508 KB |
Output is correct |
16 |
Correct |
267 ms |
26176 KB |
Output is correct |
17 |
Correct |
618 ms |
48120 KB |
Output is correct |
18 |
Correct |
36 ms |
10960 KB |
Output is correct |
19 |
Correct |
187 ms |
26644 KB |
Output is correct |
20 |
Correct |
570 ms |
48300 KB |
Output is correct |
21 |
Correct |
328 ms |
34504 KB |
Output is correct |
22 |
Correct |
162 ms |
25528 KB |
Output is correct |
23 |
Correct |
549 ms |
48256 KB |
Output is correct |
24 |
Correct |
573 ms |
48144 KB |
Output is correct |
25 |
Correct |
538 ms |
48176 KB |
Output is correct |
26 |
Correct |
189 ms |
26416 KB |
Output is correct |
27 |
Correct |
180 ms |
26524 KB |
Output is correct |
28 |
Correct |
178 ms |
26436 KB |
Output is correct |
29 |
Correct |
184 ms |
26508 KB |
Output is correct |
30 |
Correct |
180 ms |
26672 KB |
Output is correct |
31 |
Correct |
4 ms |
7380 KB |
Output is correct |
32 |
Correct |
4 ms |
7380 KB |
Output is correct |
33 |
Correct |
4 ms |
7304 KB |
Output is correct |
34 |
Correct |
4 ms |
7380 KB |
Output is correct |
35 |
Correct |
5 ms |
7380 KB |
Output is correct |
36 |
Correct |
4 ms |
7380 KB |
Output is correct |
37 |
Correct |
4 ms |
7380 KB |
Output is correct |
38 |
Correct |
3 ms |
7380 KB |
Output is correct |
39 |
Correct |
4 ms |
7380 KB |
Output is correct |
40 |
Correct |
3 ms |
7380 KB |
Output is correct |
41 |
Correct |
161 ms |
17132 KB |
Output is correct |
42 |
Correct |
386 ms |
28032 KB |
Output is correct |
43 |
Correct |
370 ms |
28184 KB |
Output is correct |
44 |
Correct |
67 ms |
12056 KB |
Output is correct |
45 |
Correct |
346 ms |
28084 KB |
Output is correct |
46 |
Correct |
364 ms |
28080 KB |
Output is correct |
47 |
Correct |
364 ms |
28008 KB |
Output is correct |
48 |
Correct |
368 ms |
28068 KB |
Output is correct |
49 |
Correct |
364 ms |
28024 KB |
Output is correct |
50 |
Correct |
351 ms |
28080 KB |
Output is correct |
51 |
Correct |
343 ms |
28104 KB |
Output is correct |
52 |
Correct |
355 ms |
28344 KB |
Output is correct |
53 |
Correct |
346 ms |
28092 KB |
Output is correct |
54 |
Correct |
365 ms |
28076 KB |
Output is correct |
55 |
Correct |
354 ms |
29172 KB |
Output is correct |
56 |
Correct |
350 ms |
28092 KB |
Output is correct |
57 |
Correct |
363 ms |
28100 KB |
Output is correct |
58 |
Correct |
408 ms |
28144 KB |
Output is correct |
59 |
Correct |
52 ms |
12064 KB |
Output is correct |
60 |
Correct |
387 ms |
28100 KB |
Output is correct |
61 |
Correct |
326 ms |
27732 KB |
Output is correct |
62 |
Correct |
67 ms |
13988 KB |
Output is correct |
63 |
Correct |
66 ms |
12576 KB |
Output is correct |
64 |
Correct |
65 ms |
13892 KB |
Output is correct |
65 |
Correct |
62 ms |
13960 KB |
Output is correct |
66 |
Correct |
78 ms |
12728 KB |
Output is correct |
67 |
Correct |
67 ms |
12064 KB |
Output is correct |
68 |
Correct |
70 ms |
13884 KB |
Output is correct |
69 |
Correct |
67 ms |
11956 KB |
Output is correct |
70 |
Correct |
64 ms |
14008 KB |
Output is correct |
71 |
Correct |
67 ms |
12028 KB |
Output is correct |
72 |
Correct |
349 ms |
36516 KB |
Output is correct |
73 |
Correct |
545 ms |
49128 KB |
Output is correct |
74 |
Correct |
547 ms |
48916 KB |
Output is correct |
75 |
Correct |
553 ms |
49104 KB |
Output is correct |
76 |
Correct |
545 ms |
48960 KB |
Output is correct |
77 |
Correct |
544 ms |
48944 KB |
Output is correct |
78 |
Correct |
545 ms |
49076 KB |
Output is correct |
79 |
Correct |
542 ms |
49036 KB |
Output is correct |
80 |
Correct |
539 ms |
48960 KB |
Output is correct |
81 |
Correct |
584 ms |
48960 KB |
Output is correct |
82 |
Correct |
543 ms |
49172 KB |
Output is correct |
83 |
Correct |
538 ms |
48944 KB |
Output is correct |
84 |
Correct |
530 ms |
48800 KB |
Output is correct |
85 |
Correct |
551 ms |
49112 KB |
Output is correct |
86 |
Correct |
553 ms |
48820 KB |
Output is correct |
87 |
Correct |
538 ms |
48816 KB |
Output is correct |
88 |
Correct |
550 ms |
48952 KB |
Output is correct |
89 |
Correct |
221 ms |
27908 KB |
Output is correct |
90 |
Correct |
541 ms |
48944 KB |
Output is correct |
91 |
Correct |
532 ms |
50800 KB |
Output is correct |
92 |
Correct |
225 ms |
28836 KB |
Output is correct |
93 |
Correct |
329 ms |
54204 KB |
Output is correct |
94 |
Correct |
228 ms |
28824 KB |
Output is correct |
95 |
Correct |
232 ms |
28992 KB |
Output is correct |
96 |
Correct |
380 ms |
57144 KB |
Output is correct |
97 |
Correct |
244 ms |
29932 KB |
Output is correct |
98 |
Correct |
248 ms |
28772 KB |
Output is correct |
99 |
Correct |
262 ms |
29912 KB |
Output is correct |
100 |
Correct |
239 ms |
28884 KB |
Output is correct |