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>
using namespace std;
#define int long long
#define FOR(a,b,c)for(int a=b;a<c;a++)
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
int p[500005];
int fs(int x)
{
if(p[x]==x)return x;
return p[x]=fs(p[x]);
}
void ms(int x,int y)
{
p[fs(x)]=fs(y);
}
int V,E,Q;
vector<pair<int,pii>>edges;
vector<pair<int,int>>adj[500005];
int ans[500005];
signed main(void)
{
ios_base::sync_with_stdio(0);cin.tie(0);
iota(p,p+500005,0);
cin>>V>>E>>Q;
FOR(i,0,E){
int a,b,q;
cin>>a>>b>>q;
edges.pb(mp(-q,mp(a,b)));
edges.pb(mp(-q,mp(b,a)));
}
sort(edges.begin(),edges.end());
for(auto e:edges){
auto &[a,b]=e.second;
if(fs(a)==fs(b))continue;
adj[a].pb(mp(b,-e.first));adj[b].pb(mp(a,-e.first));
ms(a,b);
}
queue<int>q;
FOR(i,0,500005)ans[i]=1000000;
q.push(1);
ans[1]=1000001;
while(!q.empty()){
int c=q.front();q.pop();
for(auto &[n,qu]:adj[c]){
if(ans[n]!=1000000)continue;
ans[n]=min(qu,ans[c]);
q.push(n);
}
}
FOR(i,0,Q){
int q;cin>>q;
cout<<ans[q]<<'\n';
}
}
# | 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... |