#include <bits/stdc++.h>
//#include "/Users/avaneeshk098/stdc++.h"
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define max_size 100000000
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define mod 13371337
#define w(t) int t; cin >> t; while(t--)
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define range(a,b) substr(a,b-a+1)
#define mina(a,b,c) min(a, min(b, c))
#define maxa(a,b,c) max(a, max(b, c))
#define endl '\n'
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y) for(int i = x; i < y; i++)
using namespace std;
bool sortbyfirst(const pair<int,pii> &a, const pair<int,pii> &b){ return (a.first > b.first); }
int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}
double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }
double min(double a, double b){if(a <= b){return a;} else{return b;}}
bool modd(double a, double b){if(floor(a/b) == ceil(a/b)){return true;} return false;}
bool stringsort(const string &a, const string &b){return a.length() > b.length();}
const int MN = 5e5 + 5;
vi link(MN);
vi siz(MN);
int find(int x){
if(x == link[x]) return x;
return link[x] = find(link[x]);
}
bool same(int a, int b){
return find(a) == find(b);
}
void unite(int a,int b){
a = find(a);
b = find(b);
if(siz[a] < siz[b]) swap(a,b);
siz[a] += siz[b];
link[b] = a;
}
vector<vector<pii>> adj(MN);
vi ans(MN);
vi visited(MN);
void dfs(int s, int t, int w){
if(visited[s]) return;
visited[s] = 1;
if(t != -1){
ans[s] = min(w, ans[t]);
}
for(auto i : adj[s]){
dfs(i.first, s, i.second);
}
}
void solve() {
int n,m,r;
cin >> n >> m >> r;
vector<pair<int, pii>> edg;
for(int i = 1;i <= n; i++){
ans[i] = inf;
visited[i] = 0;
}
for(int i = 0; i < m; i++){
int u,v,w;
cin >> u >> v >> w;
edg.pb({w,{u,v}});
}
for(int i = 1; i <= n; i++){ link[i] = i; siz[i] = 1;}
sort(edg.begin(), edg.end(), sortbyfirst);
for(auto e : edg){
int w = e.first, u = e.second.first, v = e.second.second;
if(!same(u,v)){
unite(u,v);
adj[u].pb({v,w});
adj[v].pb({u,w});
}
}
dfs(1,-1,0);
for(int i = 1; i <= r; i++){
int l;
cin >> l;
cout << ans[l] << endl;
}
}
int32_t main(){
FIO;
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
27724 KB |
Output is correct |
| 2 |
Correct |
17 ms |
27736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
27844 KB |
Output is correct |
| 2 |
Correct |
17 ms |
27748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
31628 KB |
Output is correct |
| 2 |
Correct |
45 ms |
31032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1969 ms |
177008 KB |
Output is correct |
| 2 |
Correct |
2905 ms |
262144 KB |
Output is correct |
