結果

問題 No.3113 The farthest point
ユーザー hot-cocoa
提出日時 2025-04-19 00:54:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,394 bytes
コンパイル時間 722 ms
コンパイル使用メモリ 78,828 KB
実行使用メモリ 32,060 KB
最終ジャッジ日時 2025-04-19 00:54:34
合計ジャッジ時間 7,159 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using int64 = long long;

template<class T>
using Graph = std::vector<std::vector<T>>;

template<class T>
class Edge {
public:
    int to;
    T weight;
    Edge(int to, T weight) : to{to}, weight{weight} {}
};

template<class Weight>
class TreeDiameter {
    Graph<Edge<Weight>> g;
    using Result = std::pair<Weight, int>;

    Result dfs(int par, int curr)
    {
        Weight max_dist = 0;
        int max_vertex = curr;

        for (const auto& [to, weight] : g[curr]) {
            if (to == par)
                continue;

            auto [dist, vertex] = dfs(curr, to);
            Weight value = dist + weight;
            
            if (value > max_dist) {
                max_dist = value;
                max_vertex = vertex;
            }
        }

        return {max_dist, max_vertex};
    }

public:
    TreeDiameter(const Graph<Edge<Weight>>& g) : g{g} {}

    Weight solve()
    {
        Result r = dfs(-1, 0);
        Result t = dfs(-1, r.second);
        return t.first;
    }
};

int main()
{
    int N;
    std::cin >> N;

    Graph<Edge<int64>> g(N);
    int64 u, v, w;
    for (int i = 0; i < N - 1; i++) {
        std::cin >> u >> v >> w;
        u--; v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    TreeDiameter<int64> tree(g);
    std::cout << tree.solve() << std::endl;
    return 0;
}
0