#include <bits/stdc++.h>
#define maxN 100005
#define maxM 500005
using namespace std;
struct edge{
int u,v,w;};
edge e[maxM];
int i,x,y,z,q,m,n,k,dg[maxN],r[maxN];
pair <int,int> par[maxN];
vector < pair<int,int> > adj[maxN];
vector <int> ans,p;
int findr(int a,int v){
while(par[a].first>=v && par[a].second!=a){
a=par[a].second;
}
return a;
}
void _union(int a,int b,int v){
int ra,rb;
ra=findr(a,v);
rb=findr(b,v);
if(ra==rb) return;
if(r[ra]<=r[rb]){
par[ra]=make_pair(v,rb);
r[rb]=max(r[rb],r[ra]+1);
}
else{
par[rb]=make_pair(v,ra);
r[ra]=max(r[ra],r[rb]+1);
}
}
void dijkstra(){
priority_queue < pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
bool mar[maxN];
int i,x;
for(i=0;i<=n;i++){
if(dg[i]==0) pq.push(make_pair(0,i));
mar[i]=false;
}
while(!pq.empty()){
x=pq.top().second;
pq.pop();
if(mar[x]) continue;
//cout<<x<<endl;
mar[x]=true;
for(i=0;i<adj[x].size();i++){
if(dg[adj[x][i].second]>dg[x]+adj[x][i].first){
dg[adj[x][i].second]=dg[x]+adj[x][i].first;
pq.push(make_pair(dg[adj[x][i].second],adj[x][i].second));
}
}
}
}
bool poredi(edge a,edge b){
return a.w>b.w;
}
bool cmp(int a,int b){
return a>b;}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(i=0;i<m;i++){
cin>>x>>y>>z;
e[i].v=x;
e[i].u=y;
adj[x].push_back(make_pair(z,y));
adj[y].push_back(make_pair(z,x));
}
for(i=0;i<=n;i++){
dg[i]=INT_MAX;
par[i]=make_pair(0,i);
r[i]=0;
}
cin>>k;
for(i=0;i<k;i++){
cin>>y;
dg[y]=0;
}
dijkstra();
for(i=1;i<=n;i++){
p.push_back(dg[i]);
}
for(i=0;i<m;i++){
e[i].w=min(dg[e[i].v],dg[e[i].u]);
}
sort(p.begin(),p.end(),cmp);
sort(e,e+m,poredi);
for(i=0;i<m;i++){
_union(e[i].v,e[i].u,e[i].w);
}
cin>>q;
for(i=0;i<q;i++){
cin>>x>>y;
int l,d,m;
l=0; d=n;
while(l!=d){
m=(l+d)/2;
if(findr(x,p[m])==findr(y,p[m])) d=m;
else l=m+1;
}
ans.push_back(p[l]);
}
for(i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
Compilation message
plan.cpp: In function 'void dijkstra()':
plan.cpp:48:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2808 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2808 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
16 |
Correct |
166 ms |
10432 KB |
Output is correct |
17 |
Correct |
533 ms |
26504 KB |
Output is correct |
18 |
Correct |
39 ms |
4880 KB |
Output is correct |
19 |
Correct |
141 ms |
11476 KB |
Output is correct |
20 |
Correct |
547 ms |
26880 KB |
Output is correct |
21 |
Correct |
263 ms |
15268 KB |
Output is correct |
22 |
Correct |
140 ms |
10828 KB |
Output is correct |
23 |
Correct |
600 ms |
26832 KB |
Output is correct |
24 |
Correct |
569 ms |
27084 KB |
Output is correct |
25 |
Correct |
549 ms |
26720 KB |
Output is correct |
26 |
Correct |
146 ms |
11504 KB |
Output is correct |
27 |
Correct |
147 ms |
11304 KB |
Output is correct |
28 |
Correct |
141 ms |
11420 KB |
Output is correct |
29 |
Correct |
142 ms |
11448 KB |
Output is correct |
30 |
Correct |
144 ms |
11728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
209 ms |
14548 KB |
Output is correct |
2 |
Correct |
483 ms |
26132 KB |
Output is correct |
3 |
Correct |
481 ms |
26252 KB |
Output is correct |
4 |
Correct |
95 ms |
9584 KB |
Output is correct |
5 |
Correct |
488 ms |
26408 KB |
Output is correct |
6 |
Correct |
493 ms |
26392 KB |
Output is correct |
7 |
Correct |
503 ms |
26224 KB |
Output is correct |
8 |
Correct |
530 ms |
26292 KB |
Output is correct |
9 |
Correct |
494 ms |
25980 KB |
Output is correct |
10 |
Correct |
497 ms |
25968 KB |
Output is correct |
11 |
Correct |
492 ms |
26940 KB |
Output is correct |
12 |
Correct |
486 ms |
26608 KB |
Output is correct |
13 |
Correct |
497 ms |
26820 KB |
Output is correct |
14 |
Correct |
482 ms |
26712 KB |
Output is correct |
15 |
Correct |
478 ms |
27976 KB |
Output is correct |
16 |
Correct |
467 ms |
26228 KB |
Output is correct |
17 |
Correct |
489 ms |
26556 KB |
Output is correct |
18 |
Correct |
513 ms |
26292 KB |
Output is correct |
19 |
Correct |
84 ms |
9332 KB |
Output is correct |
20 |
Correct |
478 ms |
26740 KB |
Output is correct |
21 |
Correct |
451 ms |
27000 KB |
Output is correct |
22 |
Correct |
107 ms |
11344 KB |
Output is correct |
23 |
Correct |
103 ms |
10132 KB |
Output is correct |
24 |
Correct |
106 ms |
11356 KB |
Output is correct |
25 |
Correct |
100 ms |
11372 KB |
Output is correct |
26 |
Correct |
108 ms |
10168 KB |
Output is correct |
27 |
Correct |
98 ms |
9844 KB |
Output is correct |
28 |
Correct |
104 ms |
11756 KB |
Output is correct |
29 |
Correct |
100 ms |
9716 KB |
Output is correct |
30 |
Correct |
106 ms |
11368 KB |
Output is correct |
31 |
Correct |
97 ms |
9664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
5 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
5 ms |
2812 KB |
Output is correct |
12 |
Correct |
5 ms |
2780 KB |
Output is correct |
13 |
Correct |
5 ms |
2808 KB |
Output is correct |
14 |
Correct |
5 ms |
2808 KB |
Output is correct |
15 |
Correct |
5 ms |
2808 KB |
Output is correct |
16 |
Correct |
166 ms |
10432 KB |
Output is correct |
17 |
Correct |
533 ms |
26504 KB |
Output is correct |
18 |
Correct |
39 ms |
4880 KB |
Output is correct |
19 |
Correct |
141 ms |
11476 KB |
Output is correct |
20 |
Correct |
547 ms |
26880 KB |
Output is correct |
21 |
Correct |
263 ms |
15268 KB |
Output is correct |
22 |
Correct |
140 ms |
10828 KB |
Output is correct |
23 |
Correct |
600 ms |
26832 KB |
Output is correct |
24 |
Correct |
569 ms |
27084 KB |
Output is correct |
25 |
Correct |
549 ms |
26720 KB |
Output is correct |
26 |
Correct |
146 ms |
11504 KB |
Output is correct |
27 |
Correct |
147 ms |
11304 KB |
Output is correct |
28 |
Correct |
141 ms |
11420 KB |
Output is correct |
29 |
Correct |
142 ms |
11448 KB |
Output is correct |
30 |
Correct |
144 ms |
11728 KB |
Output is correct |
31 |
Correct |
4 ms |
2680 KB |
Output is correct |
32 |
Correct |
4 ms |
2680 KB |
Output is correct |
33 |
Correct |
4 ms |
2680 KB |
Output is correct |
34 |
Correct |
4 ms |
2680 KB |
Output is correct |
35 |
Correct |
4 ms |
2680 KB |
Output is correct |
36 |
Correct |
4 ms |
2680 KB |
Output is correct |
37 |
Correct |
4 ms |
2680 KB |
Output is correct |
38 |
Correct |
4 ms |
2680 KB |
Output is correct |
39 |
Correct |
4 ms |
2680 KB |
Output is correct |
40 |
Correct |
4 ms |
2680 KB |
Output is correct |
41 |
Correct |
209 ms |
14548 KB |
Output is correct |
42 |
Correct |
483 ms |
26132 KB |
Output is correct |
43 |
Correct |
481 ms |
26252 KB |
Output is correct |
44 |
Correct |
95 ms |
9584 KB |
Output is correct |
45 |
Correct |
488 ms |
26408 KB |
Output is correct |
46 |
Correct |
493 ms |
26392 KB |
Output is correct |
47 |
Correct |
503 ms |
26224 KB |
Output is correct |
48 |
Correct |
530 ms |
26292 KB |
Output is correct |
49 |
Correct |
494 ms |
25980 KB |
Output is correct |
50 |
Correct |
497 ms |
25968 KB |
Output is correct |
51 |
Correct |
492 ms |
26940 KB |
Output is correct |
52 |
Correct |
486 ms |
26608 KB |
Output is correct |
53 |
Correct |
497 ms |
26820 KB |
Output is correct |
54 |
Correct |
482 ms |
26712 KB |
Output is correct |
55 |
Correct |
478 ms |
27976 KB |
Output is correct |
56 |
Correct |
467 ms |
26228 KB |
Output is correct |
57 |
Correct |
489 ms |
26556 KB |
Output is correct |
58 |
Correct |
513 ms |
26292 KB |
Output is correct |
59 |
Correct |
84 ms |
9332 KB |
Output is correct |
60 |
Correct |
478 ms |
26740 KB |
Output is correct |
61 |
Correct |
451 ms |
27000 KB |
Output is correct |
62 |
Correct |
107 ms |
11344 KB |
Output is correct |
63 |
Correct |
103 ms |
10132 KB |
Output is correct |
64 |
Correct |
106 ms |
11356 KB |
Output is correct |
65 |
Correct |
100 ms |
11372 KB |
Output is correct |
66 |
Correct |
108 ms |
10168 KB |
Output is correct |
67 |
Correct |
98 ms |
9844 KB |
Output is correct |
68 |
Correct |
104 ms |
11756 KB |
Output is correct |
69 |
Correct |
100 ms |
9716 KB |
Output is correct |
70 |
Correct |
106 ms |
11368 KB |
Output is correct |
71 |
Correct |
97 ms |
9664 KB |
Output is correct |
72 |
Correct |
285 ms |
16012 KB |
Output is correct |
73 |
Correct |
546 ms |
27228 KB |
Output is correct |
74 |
Correct |
533 ms |
27600 KB |
Output is correct |
75 |
Correct |
542 ms |
27720 KB |
Output is correct |
76 |
Correct |
562 ms |
27800 KB |
Output is correct |
77 |
Correct |
533 ms |
27588 KB |
Output is correct |
78 |
Correct |
531 ms |
27476 KB |
Output is correct |
79 |
Correct |
552 ms |
27540 KB |
Output is correct |
80 |
Correct |
520 ms |
26544 KB |
Output is correct |
81 |
Correct |
550 ms |
27004 KB |
Output is correct |
82 |
Correct |
576 ms |
26536 KB |
Output is correct |
83 |
Correct |
560 ms |
26396 KB |
Output is correct |
84 |
Correct |
562 ms |
26992 KB |
Output is correct |
85 |
Correct |
548 ms |
27960 KB |
Output is correct |
86 |
Correct |
547 ms |
27372 KB |
Output is correct |
87 |
Correct |
579 ms |
27380 KB |
Output is correct |
88 |
Correct |
533 ms |
27676 KB |
Output is correct |
89 |
Correct |
151 ms |
11452 KB |
Output is correct |
90 |
Correct |
544 ms |
27632 KB |
Output is correct |
91 |
Correct |
510 ms |
27368 KB |
Output is correct |
92 |
Correct |
142 ms |
12392 KB |
Output is correct |
93 |
Correct |
203 ms |
12048 KB |
Output is correct |
94 |
Correct |
137 ms |
12156 KB |
Output is correct |
95 |
Correct |
139 ms |
12404 KB |
Output is correct |
96 |
Correct |
198 ms |
11540 KB |
Output is correct |
97 |
Correct |
156 ms |
11332 KB |
Output is correct |
98 |
Correct |
143 ms |
12112 KB |
Output is correct |
99 |
Correct |
152 ms |
11288 KB |
Output is correct |
100 |
Correct |
143 ms |
12376 KB |
Output is correct |