This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
const int inf = 1e5+9,MX = 1e9+9;
int n,m,k,q,dis[inf],par[inf],qu[inf],qv[inf],qans[inf];
bool vis[inf];
vector<pi> adj[inf],distances;
set<pair<int,int> > s;
vector<int> queries[inf];
int root(int u){
if(u == par[u])return u;
return par[u] = root(par[u]);
}
void join(int u,int v,int Time){
u = root(u), v = root(v);
if(u == v)return ;
if(queries[u].size() > queries[v].size())
swap(u,v);
par[u] = v;
for(auto id:queries[u]){
if(qans[id] != -1)continue;
if(root(qu[id]) == root(qv[id]))
qans[id] = Time;
else
queries[v].pb(id);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adj[u].pb(pi(v,w));
adj[v].pb(pi(u,w));
}
for(int i=1;i<=n;i++)
dis[i] = MX,par[i] = i;
scanf("%d",&k);
for(int i=1;i<=k;i++){
int u;
scanf("%d",&u);
s.insert(pi(0,u));
dis[u] = 0;
}
scanf("%d",&q);
for(int i=1;i<=q;i++){
int u,v;
scanf("%d%d",&u,&v);
qu[i] = u,qv[i] = v;
queries[u].pb(i);
queries[v].pb(i);
qans[i] = -1;
}
while(!s.empty()){
int u = s.begin()->second;
s.erase(s.begin());
if(vis[u])continue;
distances.pb(pi(dis[u],u));
vis[u] = 1;
for(auto o:adj[u]){
int v = o.first,w = o.second;
if(dis[v] > dis[u] + w)
dis[v] = dis[u] + w,s.insert(pi(dis[v],v));
}
}
sort(rall(distances));
for(auto o:distances){
int Time = o.first,u = o.second;
for(auto v:adj[u])
if(dis[v.first] >= dis[u])
join(u,v.first,Time);
}
for(int i=1;i<=q;i++)
printf("%d\n",qans[i]);
}
/*
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 (stderr)
plan.cpp: In function 'int main()':
plan.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
plan.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d%d%d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d",&k);
| ~~~~~^~~~~~~~~
plan.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d",&u);
| ~~~~~^~~~~~~~~
plan.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
plan.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d%d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |