# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1085809 | 2024-09-08T18:13:09 Z | Sunbae | 관광 (NOI14_sightseeing) | C++17 | 1689 ms | 152664 KB |
#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; } } dp[0] = 1e9; dfs(0, 0); for(int u; q--; ) scanf("%d", &u), printf("%d\n", dp[--u]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 12120 KB | Output is correct |
2 | Correct | 5 ms | 12120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 12124 KB | Output is correct |
2 | Correct | 6 ms | 12172 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 15076 KB | Output is correct |
2 | Correct | 26 ms | 14684 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1068 ms | 96160 KB | Output is correct |
2 | Correct | 1689 ms | 152664 KB | Output is correct |