/*
Hasan
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MX=1e5+9;
const ll inf=(1ll<<61);
int n,m,k,q,a[MX],par[MX],sz[MX];
ll ans[MX];
ll dis[MX];
bool vis[MX];
vector<pii>v[MX];
set<int>s[MX];
int get(int x){
if(x==par[x])return x;
return par[x]=get(par[x]);
}
void mrg(int x,int y,ll cost){
x=get(x);y=get(y);
if(x==y)return;
if(sz[x]>sz[y])swap(x,y);
sz[x]+=sz[y];
par[y]=x;
if(s[x].size()<s[y].size())swap(s[x],s[y]);
for(auto pp:s[y]){
if(s[x].find(pp)!=s[x].end()){
ans[pp]=min(ans[pp],cost);
s[x].erase(pp);
continue;
}
s[x].insert(pp);
}
s[y].clear();
}
priority_queue<pair<ll,int> >pq;
void dij(){
for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
for(int i=1;i<=k;i++){
dis[a[i]]=0;
pq.push({0,a[i]});
}
while(!pq.empty()){
int x=pq.top().second;
ll c=-pq.top().first;pq.pop();
if(vis[x])continue;
vis[x]=1;
for(auto pp:v[x]){
if(dis[pp.first]>c+pp.second){
dis[pp.first]=c+pp.second;
pq.push({-dis[pp.first],pp.first});
}
}
}
}
vector<pair<ll,int> >edge;
int x,y,z;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)sz[i]=1,par[i]=i,v[i].clear(),ans[i]=0,s[i].clear();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
v[x].push_back({y,z});
v[y].push_back({x,z});
}
cin>>k;
for(int i=1;i<=k;i++)scanf("%d",&a[i]);
dij();
cin>>q;
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
if(!dis[x]||!dis[y])continue;
ans[i]=min(dis[x],dis[y]);
s[x].insert(i);
s[y].insert(i);
}
for(int i=1;i<=n;i++)edge.push_back({-dis[i],i});
sort(edge.begin(),edge.end());
for(auto pp:edge){
for(auto pp1:v[pp.second]){
if(dis[pp1.first]>=-pp.first){
mrg(pp.second,pp1.first,-pp.first);
}
}
}
edge.clear();
for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
}
/*
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:63:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:68:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=k;i++)scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
plan.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
13 ms |
7648 KB |
Output is correct |
3 |
Correct |
12 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7388 KB |
Output is correct |
5 |
Correct |
12 ms |
7544 KB |
Output is correct |
6 |
Correct |
12 ms |
7464 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
12 ms |
7544 KB |
Output is correct |
10 |
Correct |
12 ms |
7544 KB |
Output is correct |
11 |
Correct |
12 ms |
7544 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7544 KB |
Output is correct |
14 |
Correct |
12 ms |
7544 KB |
Output is correct |
15 |
Correct |
12 ms |
7544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
13 ms |
7648 KB |
Output is correct |
3 |
Correct |
12 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7388 KB |
Output is correct |
5 |
Correct |
12 ms |
7544 KB |
Output is correct |
6 |
Correct |
12 ms |
7464 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
12 ms |
7544 KB |
Output is correct |
10 |
Correct |
12 ms |
7544 KB |
Output is correct |
11 |
Correct |
12 ms |
7544 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7544 KB |
Output is correct |
14 |
Correct |
12 ms |
7544 KB |
Output is correct |
15 |
Correct |
12 ms |
7544 KB |
Output is correct |
16 |
Correct |
628 ms |
24904 KB |
Output is correct |
17 |
Correct |
1102 ms |
37068 KB |
Output is correct |
18 |
Correct |
81 ms |
10484 KB |
Output is correct |
19 |
Correct |
552 ms |
27800 KB |
Output is correct |
20 |
Correct |
1119 ms |
37128 KB |
Output is correct |
21 |
Correct |
582 ms |
22760 KB |
Output is correct |
22 |
Correct |
481 ms |
24908 KB |
Output is correct |
23 |
Correct |
1091 ms |
37100 KB |
Output is correct |
24 |
Correct |
1093 ms |
37192 KB |
Output is correct |
25 |
Correct |
1048 ms |
35400 KB |
Output is correct |
26 |
Correct |
549 ms |
27728 KB |
Output is correct |
27 |
Correct |
562 ms |
27728 KB |
Output is correct |
28 |
Correct |
550 ms |
27784 KB |
Output is correct |
29 |
Correct |
539 ms |
27820 KB |
Output is correct |
30 |
Correct |
546 ms |
27896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7360 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
8 ms |
7368 KB |
Output is correct |
6 |
Correct |
9 ms |
7416 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7388 KB |
Output is correct |
9 |
Correct |
8 ms |
7416 KB |
Output is correct |
10 |
Correct |
8 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
19388 KB |
Output is correct |
2 |
Correct |
565 ms |
29064 KB |
Output is correct |
3 |
Correct |
551 ms |
28900 KB |
Output is correct |
4 |
Correct |
111 ms |
15188 KB |
Output is correct |
5 |
Correct |
564 ms |
28936 KB |
Output is correct |
6 |
Correct |
525 ms |
29028 KB |
Output is correct |
7 |
Correct |
534 ms |
28928 KB |
Output is correct |
8 |
Correct |
569 ms |
28908 KB |
Output is correct |
9 |
Correct |
561 ms |
28872 KB |
Output is correct |
10 |
Correct |
566 ms |
29020 KB |
Output is correct |
11 |
Correct |
576 ms |
28864 KB |
Output is correct |
12 |
Correct |
545 ms |
29020 KB |
Output is correct |
13 |
Correct |
559 ms |
28920 KB |
Output is correct |
14 |
Correct |
545 ms |
28900 KB |
Output is correct |
15 |
Correct |
561 ms |
29596 KB |
Output is correct |
16 |
Correct |
573 ms |
28872 KB |
Output is correct |
17 |
Correct |
603 ms |
28968 KB |
Output is correct |
18 |
Correct |
551 ms |
28916 KB |
Output is correct |
19 |
Correct |
103 ms |
15084 KB |
Output is correct |
20 |
Correct |
574 ms |
28980 KB |
Output is correct |
21 |
Correct |
555 ms |
28528 KB |
Output is correct |
22 |
Correct |
123 ms |
18404 KB |
Output is correct |
23 |
Correct |
113 ms |
15592 KB |
Output is correct |
24 |
Correct |
119 ms |
18432 KB |
Output is correct |
25 |
Correct |
128 ms |
18436 KB |
Output is correct |
26 |
Correct |
126 ms |
15764 KB |
Output is correct |
27 |
Correct |
104 ms |
15192 KB |
Output is correct |
28 |
Correct |
121 ms |
18404 KB |
Output is correct |
29 |
Correct |
119 ms |
15088 KB |
Output is correct |
30 |
Correct |
123 ms |
18436 KB |
Output is correct |
31 |
Correct |
111 ms |
15152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
13 ms |
7648 KB |
Output is correct |
3 |
Correct |
12 ms |
7544 KB |
Output is correct |
4 |
Correct |
8 ms |
7388 KB |
Output is correct |
5 |
Correct |
12 ms |
7544 KB |
Output is correct |
6 |
Correct |
12 ms |
7464 KB |
Output is correct |
7 |
Correct |
8 ms |
7416 KB |
Output is correct |
8 |
Correct |
8 ms |
7416 KB |
Output is correct |
9 |
Correct |
12 ms |
7544 KB |
Output is correct |
10 |
Correct |
12 ms |
7544 KB |
Output is correct |
11 |
Correct |
12 ms |
7544 KB |
Output is correct |
12 |
Correct |
14 ms |
7672 KB |
Output is correct |
13 |
Correct |
14 ms |
7544 KB |
Output is correct |
14 |
Correct |
12 ms |
7544 KB |
Output is correct |
15 |
Correct |
12 ms |
7544 KB |
Output is correct |
16 |
Correct |
628 ms |
24904 KB |
Output is correct |
17 |
Correct |
1102 ms |
37068 KB |
Output is correct |
18 |
Correct |
81 ms |
10484 KB |
Output is correct |
19 |
Correct |
552 ms |
27800 KB |
Output is correct |
20 |
Correct |
1119 ms |
37128 KB |
Output is correct |
21 |
Correct |
582 ms |
22760 KB |
Output is correct |
22 |
Correct |
481 ms |
24908 KB |
Output is correct |
23 |
Correct |
1091 ms |
37100 KB |
Output is correct |
24 |
Correct |
1093 ms |
37192 KB |
Output is correct |
25 |
Correct |
1048 ms |
35400 KB |
Output is correct |
26 |
Correct |
549 ms |
27728 KB |
Output is correct |
27 |
Correct |
562 ms |
27728 KB |
Output is correct |
28 |
Correct |
550 ms |
27784 KB |
Output is correct |
29 |
Correct |
539 ms |
27820 KB |
Output is correct |
30 |
Correct |
546 ms |
27896 KB |
Output is correct |
31 |
Correct |
8 ms |
7416 KB |
Output is correct |
32 |
Correct |
8 ms |
7416 KB |
Output is correct |
33 |
Correct |
8 ms |
7360 KB |
Output is correct |
34 |
Correct |
8 ms |
7416 KB |
Output is correct |
35 |
Correct |
8 ms |
7368 KB |
Output is correct |
36 |
Correct |
9 ms |
7416 KB |
Output is correct |
37 |
Correct |
8 ms |
7416 KB |
Output is correct |
38 |
Correct |
8 ms |
7388 KB |
Output is correct |
39 |
Correct |
8 ms |
7416 KB |
Output is correct |
40 |
Correct |
8 ms |
7416 KB |
Output is correct |
41 |
Correct |
252 ms |
19388 KB |
Output is correct |
42 |
Correct |
565 ms |
29064 KB |
Output is correct |
43 |
Correct |
551 ms |
28900 KB |
Output is correct |
44 |
Correct |
111 ms |
15188 KB |
Output is correct |
45 |
Correct |
564 ms |
28936 KB |
Output is correct |
46 |
Correct |
525 ms |
29028 KB |
Output is correct |
47 |
Correct |
534 ms |
28928 KB |
Output is correct |
48 |
Correct |
569 ms |
28908 KB |
Output is correct |
49 |
Correct |
561 ms |
28872 KB |
Output is correct |
50 |
Correct |
566 ms |
29020 KB |
Output is correct |
51 |
Correct |
576 ms |
28864 KB |
Output is correct |
52 |
Correct |
545 ms |
29020 KB |
Output is correct |
53 |
Correct |
559 ms |
28920 KB |
Output is correct |
54 |
Correct |
545 ms |
28900 KB |
Output is correct |
55 |
Correct |
561 ms |
29596 KB |
Output is correct |
56 |
Correct |
573 ms |
28872 KB |
Output is correct |
57 |
Correct |
603 ms |
28968 KB |
Output is correct |
58 |
Correct |
551 ms |
28916 KB |
Output is correct |
59 |
Correct |
103 ms |
15084 KB |
Output is correct |
60 |
Correct |
574 ms |
28980 KB |
Output is correct |
61 |
Correct |
555 ms |
28528 KB |
Output is correct |
62 |
Correct |
123 ms |
18404 KB |
Output is correct |
63 |
Correct |
113 ms |
15592 KB |
Output is correct |
64 |
Correct |
119 ms |
18432 KB |
Output is correct |
65 |
Correct |
128 ms |
18436 KB |
Output is correct |
66 |
Correct |
126 ms |
15764 KB |
Output is correct |
67 |
Correct |
104 ms |
15192 KB |
Output is correct |
68 |
Correct |
121 ms |
18404 KB |
Output is correct |
69 |
Correct |
119 ms |
15088 KB |
Output is correct |
70 |
Correct |
123 ms |
18436 KB |
Output is correct |
71 |
Correct |
111 ms |
15152 KB |
Output is correct |
72 |
Correct |
818 ms |
28696 KB |
Output is correct |
73 |
Correct |
1135 ms |
37052 KB |
Output is correct |
74 |
Correct |
1128 ms |
37224 KB |
Output is correct |
75 |
Correct |
1097 ms |
37060 KB |
Output is correct |
76 |
Correct |
1115 ms |
37116 KB |
Output is correct |
77 |
Correct |
1211 ms |
37112 KB |
Output is correct |
78 |
Correct |
1135 ms |
37048 KB |
Output is correct |
79 |
Correct |
1121 ms |
37156 KB |
Output is correct |
80 |
Correct |
1144 ms |
37092 KB |
Output is correct |
81 |
Correct |
1099 ms |
37092 KB |
Output is correct |
82 |
Correct |
1116 ms |
37012 KB |
Output is correct |
83 |
Correct |
1101 ms |
36964 KB |
Output is correct |
84 |
Correct |
1080 ms |
36356 KB |
Output is correct |
85 |
Correct |
1072 ms |
36408 KB |
Output is correct |
86 |
Correct |
1090 ms |
36856 KB |
Output is correct |
87 |
Correct |
1130 ms |
37176 KB |
Output is correct |
88 |
Correct |
1241 ms |
37200 KB |
Output is correct |
89 |
Correct |
659 ms |
24996 KB |
Output is correct |
90 |
Correct |
1114 ms |
37136 KB |
Output is correct |
91 |
Correct |
816 ms |
28616 KB |
Output is correct |
92 |
Correct |
651 ms |
27772 KB |
Output is correct |
93 |
Correct |
787 ms |
25584 KB |
Output is correct |
94 |
Correct |
645 ms |
27680 KB |
Output is correct |
95 |
Correct |
633 ms |
27716 KB |
Output is correct |
96 |
Correct |
848 ms |
25168 KB |
Output is correct |
97 |
Correct |
693 ms |
24632 KB |
Output is correct |
98 |
Correct |
643 ms |
27652 KB |
Output is correct |
99 |
Correct |
676 ms |
24652 KB |
Output is correct |
100 |
Correct |
616 ms |
27724 KB |
Output is correct |