結果
問題 |
No.3113 The farthest point
|
ユーザー |
![]() |
提出日時 | 2025-04-18 21:27:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,595 bytes |
コンパイル時間 | 5,512 ms |
コンパイル使用メモリ | 332,308 KB |
実行使用メモリ | 23,020 KB |
最終ジャッジ日時 | 2025-04-18 21:27:27 |
合計ジャッジ時間 | 8,635 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 WA * 13 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; pair<int, i64> farthest_node(int start, const vector<vector<pair<int, i64>>>& g) { vector<i64> dist(g.size(), INF); int N = g.size(); vector<bool> visited(N); queue<int> q; q.push(start); visited[start] = true; dist[start] = 0; int farthest = start; i64 max_dist = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (auto [next, weight] : g[node]) { if (!visited[next]) { visited[next] = true; dist[next] = dist[node] + weight; q.push(next); if (dist[next] > max_dist) { max_dist = dist[next]; farthest = next; } } } } return {farthest, max_dist}; } i64 diameter(const vector<vector<pair<int, i64>>>& g) { int N = g.size(); auto [farthest, _] = farthest_node(0, g); return farthest_node(farthest, g).second; } int main() { FAST_IO auto ans = 0LL; int N; cin >> N; vector<int> u(N-1), v(N-1); vector<i64> w(N-1); for (int i = 0; i < N - 1; i ++) { cin >> u[i] >> v[i] >> w[i]; u[i] --; v[i] --; } vector<vector<pair<int, i64>>> g(N); for (int i = 0; i < N - 1; i ++) { g[u[i]].emplace_back(v[i], w[i]); g[v[i]].emplace_back(u[i], w[i]); } ans = diameter(g); cout << ans << endl; }