#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct adj_edge {
int v, w;
bool operator<(const adj_edge &other) const {
return w < other.w;
}
};
struct list_edge {
int u, v, w;
bool operator<(const list_edge &other) const {
return w < other.w;
}
};
int V, E, Q;
vector< vector<adj_edge> > adj;
vector<list_edge> edge_list;
vector<int> par, dist;
int find(int u) {
if (par[u] == u)
return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
int ru = find(u), rv = find(v);
if (ru == rv)
return;
if (rand()%2)
swap(ru, rv);
par[ru] = rv;
}
void kruskall() {
for (int i = 0; i < V; ++i)
par.push_back(i);
sort(edge_list.rbegin(), edge_list.rend());
for (list_edge e: edge_list) {
if (find(e.u) == find(e.v))
continue;
merge(e.u, e.v);
adj[e.u].push_back({e.v, e.w});
adj[e.v].push_back({e.u, e.w});
}
}
void dfs(int cur, int curmin) {
if (dist[cur] != -1)
return;
dist[cur] = curmin;
for (adj_edge e: adj[cur]) {
dfs(e.v, min(curmin, e.w));
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> V >> E >> Q;
adj.resize(V);
for (int e = 0; e < E; ++e) {
int u, v, q;
cin >> u >> v >> q;
edge_list.push_back({u-1, v-1, q});
}
kruskall();
dist.assign(V, -1);
dfs(0, INF);
for (int q = 0; q < Q; ++q) {
int X;
cin >> X;
cout << dist[X-1] << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
50 ms |
3168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2680 ms |
62108 KB |
Output is correct |
| 2 |
Execution timed out |
3519 ms |
113712 KB |
Time limit exceeded |
