#include<bits/stdc++.h>
using namespace std;
/*ifstream fin("evacplan.in");
ofstream fout("evacplan.out");
#define cin fin
#define cout fout*/
const int INF = 1e9;
int n,m,k,q,pas;
int father[100005];
int rez[100005];
bool done[100005];
vector<pair<pair<int,int>,int>> qrys[100005];
int dist[100005];
pair<int,int> v[100005];
vector<pair<int,int>> con[100005];
priority_queue<pair<int,int>> pq;
void dijkstra()
{
while(!pq.empty())
{
int nod = pq.top().second;
int cdist = -pq.top().first;
pq.pop();
if(dist[nod]!=cdist)
continue;
for(auto x:con[nod])
{
if(dist[x.first] > dist[nod] + x.second)
{
dist[x.first] = dist[nod] + x.second;
pq.push({-dist[x.first], x.first});
}
}
}
}
int gas(int x)
{
if(father[x]!=x)
father[x]=gas(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = gas(x);
y = gas(y);
if(x==y)
return;
if((int)qrys[x].size() < (int)qrys[y].size())
swap(x,y);
for(auto z:qrys[y])
{
if(gas(z.first.second)==x && !done[z.second])
{
done[z.second]=1;
rez[z.second]=pas;
}
else
qrys[x].push_back(z);
}
qrys[y].clear();
father[y]=x;
}
signed main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
int a,b,w;
for(int i=0;i<m;i++)
{
cin>>a>>b>>w;
con[a].push_back({b,w});
con[b].push_back({a,w});
}
for(int i=1;i<=n;i++)
dist[i]=INF;
cin>>k;
for(int i=0;i<k;i++)
{
cin>>a;
dist[a]=0;
pq.push({0,a});
}
dijkstra();
for(int i=1;i<=n;i++)
{
v[i] = {dist[i], i};
father[i]=i;
}
sort(v+1,v+1+n);
cin>>q;
for(int i=0;i<q;i++)
{
cin>>a>>b;
if(a==b)
{
rez[i] = dist[a];
}
else
{
qrys[a].push_back({{a,b},i});
qrys[b].push_back({{b,a},i});
}
}
for(int i=n;i>0;i--)
{
pas = v[i].first;
int x = v[i].second;
for(auto adj:con[x])
if(dist[adj.first] >= dist[x])
unite(x, adj.first);
}
for(int i=0;i<q;i++)
cout<<rez[i]<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6744 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
3 ms |
6748 KB |
Output is correct |
10 |
Correct |
3 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6932 KB |
Output is correct |
12 |
Correct |
2 ms |
6756 KB |
Output is correct |
13 |
Correct |
3 ms |
6748 KB |
Output is correct |
14 |
Correct |
2 ms |
6780 KB |
Output is correct |
15 |
Correct |
3 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6744 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
3 ms |
6748 KB |
Output is correct |
10 |
Correct |
3 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6932 KB |
Output is correct |
12 |
Correct |
2 ms |
6756 KB |
Output is correct |
13 |
Correct |
3 ms |
6748 KB |
Output is correct |
14 |
Correct |
2 ms |
6780 KB |
Output is correct |
15 |
Correct |
3 ms |
6748 KB |
Output is correct |
16 |
Correct |
163 ms |
20252 KB |
Output is correct |
17 |
Correct |
550 ms |
36596 KB |
Output is correct |
18 |
Correct |
38 ms |
9328 KB |
Output is correct |
19 |
Correct |
177 ms |
19340 KB |
Output is correct |
20 |
Correct |
506 ms |
36852 KB |
Output is correct |
21 |
Correct |
256 ms |
25028 KB |
Output is correct |
22 |
Correct |
149 ms |
18420 KB |
Output is correct |
23 |
Correct |
562 ms |
36568 KB |
Output is correct |
24 |
Correct |
548 ms |
37020 KB |
Output is correct |
25 |
Correct |
541 ms |
36804 KB |
Output is correct |
26 |
Correct |
171 ms |
19272 KB |
Output is correct |
27 |
Correct |
170 ms |
19260 KB |
Output is correct |
28 |
Correct |
149 ms |
19268 KB |
Output is correct |
29 |
Correct |
189 ms |
19356 KB |
Output is correct |
30 |
Correct |
153 ms |
19432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6944 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6748 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6760 KB |
Output is correct |
9 |
Correct |
2 ms |
6760 KB |
Output is correct |
10 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
186 ms |
14052 KB |
Output is correct |
2 |
Correct |
450 ms |
30220 KB |
Output is correct |
3 |
Correct |
433 ms |
30320 KB |
Output is correct |
4 |
Correct |
87 ms |
11860 KB |
Output is correct |
5 |
Correct |
461 ms |
30196 KB |
Output is correct |
6 |
Correct |
422 ms |
30324 KB |
Output is correct |
7 |
Correct |
417 ms |
30324 KB |
Output is correct |
8 |
Correct |
465 ms |
30264 KB |
Output is correct |
9 |
Correct |
445 ms |
30232 KB |
Output is correct |
10 |
Correct |
404 ms |
30376 KB |
Output is correct |
11 |
Correct |
454 ms |
30248 KB |
Output is correct |
12 |
Correct |
409 ms |
30404 KB |
Output is correct |
13 |
Correct |
442 ms |
30316 KB |
Output is correct |
14 |
Correct |
457 ms |
30712 KB |
Output is correct |
15 |
Correct |
418 ms |
30912 KB |
Output is correct |
16 |
Correct |
455 ms |
30268 KB |
Output is correct |
17 |
Correct |
406 ms |
30192 KB |
Output is correct |
18 |
Correct |
412 ms |
30296 KB |
Output is correct |
19 |
Correct |
83 ms |
11860 KB |
Output is correct |
20 |
Correct |
462 ms |
30444 KB |
Output is correct |
21 |
Correct |
428 ms |
30412 KB |
Output is correct |
22 |
Correct |
95 ms |
13768 KB |
Output is correct |
23 |
Correct |
96 ms |
12232 KB |
Output is correct |
24 |
Correct |
95 ms |
13692 KB |
Output is correct |
25 |
Correct |
90 ms |
13760 KB |
Output is correct |
26 |
Correct |
91 ms |
12576 KB |
Output is correct |
27 |
Correct |
86 ms |
11980 KB |
Output is correct |
28 |
Correct |
92 ms |
13764 KB |
Output is correct |
29 |
Correct |
79 ms |
11860 KB |
Output is correct |
30 |
Correct |
89 ms |
13768 KB |
Output is correct |
31 |
Correct |
82 ms |
11708 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
6744 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6744 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
3 ms |
6748 KB |
Output is correct |
10 |
Correct |
3 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6932 KB |
Output is correct |
12 |
Correct |
2 ms |
6756 KB |
Output is correct |
13 |
Correct |
3 ms |
6748 KB |
Output is correct |
14 |
Correct |
2 ms |
6780 KB |
Output is correct |
15 |
Correct |
3 ms |
6748 KB |
Output is correct |
16 |
Correct |
163 ms |
20252 KB |
Output is correct |
17 |
Correct |
550 ms |
36596 KB |
Output is correct |
18 |
Correct |
38 ms |
9328 KB |
Output is correct |
19 |
Correct |
177 ms |
19340 KB |
Output is correct |
20 |
Correct |
506 ms |
36852 KB |
Output is correct |
21 |
Correct |
256 ms |
25028 KB |
Output is correct |
22 |
Correct |
149 ms |
18420 KB |
Output is correct |
23 |
Correct |
562 ms |
36568 KB |
Output is correct |
24 |
Correct |
548 ms |
37020 KB |
Output is correct |
25 |
Correct |
541 ms |
36804 KB |
Output is correct |
26 |
Correct |
171 ms |
19272 KB |
Output is correct |
27 |
Correct |
170 ms |
19260 KB |
Output is correct |
28 |
Correct |
149 ms |
19268 KB |
Output is correct |
29 |
Correct |
189 ms |
19356 KB |
Output is correct |
30 |
Correct |
153 ms |
19432 KB |
Output is correct |
31 |
Correct |
2 ms |
6748 KB |
Output is correct |
32 |
Correct |
1 ms |
6748 KB |
Output is correct |
33 |
Correct |
2 ms |
6944 KB |
Output is correct |
34 |
Correct |
1 ms |
6748 KB |
Output is correct |
35 |
Correct |
2 ms |
6748 KB |
Output is correct |
36 |
Correct |
1 ms |
6748 KB |
Output is correct |
37 |
Correct |
2 ms |
6748 KB |
Output is correct |
38 |
Correct |
1 ms |
6760 KB |
Output is correct |
39 |
Correct |
2 ms |
6760 KB |
Output is correct |
40 |
Correct |
1 ms |
6748 KB |
Output is correct |
41 |
Correct |
186 ms |
14052 KB |
Output is correct |
42 |
Correct |
450 ms |
30220 KB |
Output is correct |
43 |
Correct |
433 ms |
30320 KB |
Output is correct |
44 |
Correct |
87 ms |
11860 KB |
Output is correct |
45 |
Correct |
461 ms |
30196 KB |
Output is correct |
46 |
Correct |
422 ms |
30324 KB |
Output is correct |
47 |
Correct |
417 ms |
30324 KB |
Output is correct |
48 |
Correct |
465 ms |
30264 KB |
Output is correct |
49 |
Correct |
445 ms |
30232 KB |
Output is correct |
50 |
Correct |
404 ms |
30376 KB |
Output is correct |
51 |
Correct |
454 ms |
30248 KB |
Output is correct |
52 |
Correct |
409 ms |
30404 KB |
Output is correct |
53 |
Correct |
442 ms |
30316 KB |
Output is correct |
54 |
Correct |
457 ms |
30712 KB |
Output is correct |
55 |
Correct |
418 ms |
30912 KB |
Output is correct |
56 |
Correct |
455 ms |
30268 KB |
Output is correct |
57 |
Correct |
406 ms |
30192 KB |
Output is correct |
58 |
Correct |
412 ms |
30296 KB |
Output is correct |
59 |
Correct |
83 ms |
11860 KB |
Output is correct |
60 |
Correct |
462 ms |
30444 KB |
Output is correct |
61 |
Correct |
428 ms |
30412 KB |
Output is correct |
62 |
Correct |
95 ms |
13768 KB |
Output is correct |
63 |
Correct |
96 ms |
12232 KB |
Output is correct |
64 |
Correct |
95 ms |
13692 KB |
Output is correct |
65 |
Correct |
90 ms |
13760 KB |
Output is correct |
66 |
Correct |
91 ms |
12576 KB |
Output is correct |
67 |
Correct |
86 ms |
11980 KB |
Output is correct |
68 |
Correct |
92 ms |
13764 KB |
Output is correct |
69 |
Correct |
79 ms |
11860 KB |
Output is correct |
70 |
Correct |
89 ms |
13768 KB |
Output is correct |
71 |
Correct |
82 ms |
11708 KB |
Output is correct |
72 |
Correct |
248 ms |
24872 KB |
Output is correct |
73 |
Correct |
490 ms |
36764 KB |
Output is correct |
74 |
Correct |
510 ms |
36800 KB |
Output is correct |
75 |
Correct |
494 ms |
36808 KB |
Output is correct |
76 |
Correct |
535 ms |
37556 KB |
Output is correct |
77 |
Correct |
485 ms |
36808 KB |
Output is correct |
78 |
Correct |
490 ms |
36900 KB |
Output is correct |
79 |
Correct |
534 ms |
36952 KB |
Output is correct |
80 |
Correct |
579 ms |
36800 KB |
Output is correct |
81 |
Correct |
515 ms |
37112 KB |
Output is correct |
82 |
Correct |
507 ms |
36868 KB |
Output is correct |
83 |
Correct |
498 ms |
36808 KB |
Output is correct |
84 |
Correct |
499 ms |
36712 KB |
Output is correct |
85 |
Correct |
518 ms |
37784 KB |
Output is correct |
86 |
Correct |
593 ms |
36836 KB |
Output is correct |
87 |
Correct |
486 ms |
36664 KB |
Output is correct |
88 |
Correct |
556 ms |
36760 KB |
Output is correct |
89 |
Correct |
170 ms |
19404 KB |
Output is correct |
90 |
Correct |
585 ms |
36696 KB |
Output is correct |
91 |
Correct |
522 ms |
36952 KB |
Output is correct |
92 |
Correct |
158 ms |
21144 KB |
Output is correct |
93 |
Correct |
174 ms |
28420 KB |
Output is correct |
94 |
Correct |
177 ms |
21372 KB |
Output is correct |
95 |
Correct |
156 ms |
21068 KB |
Output is correct |
96 |
Correct |
182 ms |
29232 KB |
Output is correct |
97 |
Correct |
173 ms |
20028 KB |
Output is correct |
98 |
Correct |
162 ms |
21128 KB |
Output is correct |
99 |
Correct |
210 ms |
20348 KB |
Output is correct |
100 |
Correct |
163 ms |
21100 KB |
Output is correct |