結果
問題 | No.3113 The farthest point |
ユーザー |
![]() |
提出日時 | 2025-04-19 09:37:08 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 1,237 bytes |
コンパイル時間 | 1,713 ms |
コンパイル使用メモリ | 144,996 KB |
実行使用メモリ | 18,108 KB |
最終ジャッジ日時 | 2025-04-19 09:37:24 |
合計ジャッジ時間 | 8,452 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <string> #include <map> #include <set> #include <limits> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) typedef long long ll; template<typename T> struct Edge { int to; T cost; }; template<typename T> using WeightedGraph = vector<vector<Edge<T>>>; template<typename T> T dfs(const WeightedGraph<T> &g, int u, int parent, T &result) { T best1 = 0; T best2 = 0; for(auto &e : g[u]) { if(e.to == parent) continue; T child_best = dfs(g, e.to, u, result) + e.cost; if(child_best > best1) { best2 = best1; best1 = child_best; } else if(child_best > best2) { best2 = child_best; } } result = max(result, best1 + best2); return best1; } template< typename T > T tree_diameter(const WeightedGraph<T> &g) { if (g.size() <= 1) return 0; T result = numeric_limits<T>::lowest(); dfs(g, 0, -1, result); return result; } signed main() { int N; cin >> N; WeightedGraph<ll> g(N); rep(i, N - 1) { int u, v; ll w; cin >> u >> v >> w; u--; v--; g[u].emplace_back(Edge<ll>{v, w}); g[v].emplace_back(Edge<ll>{u, w}); } cout << tree_diameter(g) << endl; }