#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
const int N = 5e5 + 5, M = 5e6 + 5;
int sz[N], p[N], dp[N];
tuple<int,int,int> e[M];
vector<pair<int,int>> g[N];
void dfs(int u, int p){
for(pair<int,int> it: g[u]){
int w = it.first, v = it.second;
if(v != p) dp[v] = min(w, dp[u]), dfs(v, u);
}
}
int fp(int u){ return u == p[u] ? u : p[u] = fp(p[u]);}
signed main(){
int n, m, q; scanf("%d %d %d", &n, &m, &q);
for(int i = 0; i<n; ++i) p[i] = i, sz[i] = 1;
for(int i = 0, u, v, w; i<m; ++i){
scanf("%d %d %d", &u, &v, &w); --u; --v;
e[i] = make_tuple(-w, u, v);
}
sort(e, e+m);
for(int i = 0; i<m; ++i){
int w, u, v; tie(w, u, v) = e[i]; w = -w;
if(fp(u) != fp(v)){
g[u].emplace_back(w, v);
g[v].emplace_back(w, u);
u = fp(u); v = fp(v);
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v]; sz[v] = 0;
p[v] = u;
}
}
fill(dp, dp+n, 1e9);
dfs(0, 0);
for(int u; q--; ) scanf("%d", &u), printf("%d\n", dp[--u]);
}
Compilation message
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | int n, m, q; scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | scanf("%d %d %d", &u, &v, &w); --u; --v;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:41:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | for(int u; q--; ) scanf("%d", &u), printf("%d\n", dp[--u]);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12124 KB |
Output is correct |
2 |
Correct |
5 ms |
12124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12248 KB |
Output is correct |
2 |
Correct |
5 ms |
12124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
15452 KB |
Output is correct |
2 |
Correct |
24 ms |
14940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1055 ms |
125104 KB |
Output is correct |
2 |
Correct |
1625 ms |
202580 KB |
Output is correct |