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 int long long
#define INT_MAX LONG_LONG_MAX
#define pii pair<int,pair<int,int> >
#define x first
#define y second.first
#define z second.second
using namespace std;
int n,m,N,q,ans[100005];
map<pair<int,int>,int> mp;
vector<int> g[100005],d,used,p,Size;
multiset<pair<int,int> > s;
vector<pii> Q,ed;
bool comp_sort(pii a,pii b){
return min(d[a.x],d[a.y])>min(d[b.x],d[b.y]);
}
void MS(){
for(int k=1;k<=n;k++){
p[k]=k;
Size[k]=d[k];
}
return;
}
int FS(int v){
if(p[v]==v) return v;
return p[v]=FS(p[v]);
}
void US(int a,int b){
a=FS(a);
b=FS(b);
if(a!=b){
p[b]=a;
Size[a]=min(Size[a],Size[b]);
}
}
main(){
cin>>n>>m;
for(int k=1;k<=m;k++){
int a,b,c;
cin>>a>>b>>c;
mp[{a,b}]=c;
mp[{b,a}]=c;
g[a].push_back(b);
g[b].push_back(a);
}
cin>>N;
d.resize(n+1,INT_MAX);
used.resize(n+1,0);
for(int k=1;k<=N;k++){
int qal;
cin>>qal;
d[qal]=0;
s.insert({0,qal});
}
while(!s.empty()){
int v=s.begin()->second;
used[v]=1;
s.erase(s.begin());
for(int k=0;k<g[v].size();k++){
int to=g[v][k];
if(used[to]==0 && d[to]>d[v]+mp[{v,to}]){
d[to]=d[v]+mp[{to,v}];
s.insert({d[to],to});
}
}
}
for(int k=1;k<=n;k++){
ed.push_back({d[k],{k,0}});
}
sort(ed.begin(),ed.end());
reverse(ed.begin(),ed.end());
cin>>q;
for(int k=1;k<=q;k++){
int a,b;
cin>>a>>b;
if(d[a]>d[b])
swap(a,b);
Q.push_back({a,{b,k}});
}
int j=0;
sort(Q.begin(),Q.end(),comp_sort);
Size.resize(n+1,0);
p.resize(n+1,0);
used.resize(0);
used.resize(n+1,0);
MS();
for(int k=0;k<ed.size();k++){
int v=ed[k].y;
used[v]=1;
for(int k=0;k<g[v].size();k++)
if(used[g[v][k]])
US(v,g[v][k]);
for(int i=0;i<Q.size();i++){
if(FS(Q[i].x)==FS(Q[i].y))
ans[Q[i].z]=max(ans[Q[i].z],Size[FS(Q[i].x)]);
}
}
for(int k=1;k<=q;k++)
cout<<ans[k]<<endl;
return 0;
}
Compilation message (stderr)
plan.cpp:3:0: warning: "INT_MAX" redefined
#define INT_MAX LONG_LONG_MAX
In file included from /usr/include/c++/7/climits:42:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:39,
from plan.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/7/include-fixed/limits.h:120:0: note: this is the location of the previous definition
#define INT_MAX __INT_MAX__
plan.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
plan.cpp: In function 'int main()':
plan.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[v].size();k++){
~^~~~~~~~~~~~
plan.cpp:87:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ed.size();k++){
~^~~~~~~~~~
plan.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<g[v].size();k++)
~^~~~~~~~~~~~
plan.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Q.size();i++){
~^~~~~~~~~
plan.cpp:80:5: warning: unused variable 'j' [-Wunused-variable]
int j=0;
^
# | 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... |