#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
#define mp make_pair
const int MAXV = 5e5 + 7;
const int INF = 1e9 + 7;
vector<pii> adj[MAXV];
int parent[MAXV], ans[MAXV];
int find(int u){
if(parent[u] == u)
return u;
return parent[u] = find(parent[u]);
}
void merge(int x, int y){
x = find(x);
y = find(y);
parent[x] = y;
}
void dfs(int x, int y){
for(auto temp : adj[x]){
int z = temp.first, w = temp.second;
if(y != z){
ans[z] = min(ans[x], w);
dfs(z, x);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int v, e, q;
cin >> v >> e >> q;
pair<int, pii> edges[e];
for(int i = 0; i < e; i++){
int x, y, z;
cin >> x >> y >> z;
edges[i].first = z;
edges[i].second.first = x;
edges[i].second.second = y;
}
sort(edges, edges + e);
reverse(edges, edges + e);
for(int i = 1; i <= v; i++)
parent[i] = i;
for(auto u : edges){
int wt = u.first, x = u.second.first, y = u.second.second;
int a = find(x);
int b = find(y);
if(a != b){
adj[x].push_back(mp(y, wt));
adj[y].push_back(mp(x, wt));
merge(x, y);
}
}
ans[1] = INF;
dfs(1, -1);
for(int i = 0; i < q; i++){
int u;
cin >> u;
cout << ans[u] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
15076 KB |
Output is correct |
| 2 |
Correct |
39 ms |
14772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1829 ms |
123672 KB |
Output is correct |
| 2 |
Correct |
2811 ms |
200632 KB |
Output is correct |
