結果

問題 No.3113 The farthest point
ユーザー よいちなすの
提出日時 2025-04-18 21:38:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,372 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 72,408 KB
実行使用メモリ 15,248 KB
最終ジャッジ日時 2025-04-18 21:38:38
合計ジャッジ時間 6,009 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 1 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int to, weight;
};

int N; // 頂点の数
vector<vector<Edge>> graph;

pair<int, int> dfs(int v, int parent) {
    pair<int, int> farthest = {0, v}; // {最長距離, 頂点番号}
    
    for (const Edge& edge : graph[v]) {
        if (edge.to == parent) continue; // 親ノードには戻らない
        pair<int, int> result = dfs(edge.to, v);
        result.first += edge.weight; // 頂点 v から子ノードへの距離を加算
        if (result.first > farthest.first) {
            farthest = result; // 最長距離を更新
        }
    }

    return farthest;
}

int main() {
    cin >> N;
    graph.resize(N);
    
    // 辺の入力
    for (int i = 0; i < N - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 0-indexedに調整
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    // 任意の頂点（0）から最も遠い頂点を見つける
    pair<int, int> farthest_from_start = dfs(0, -1);

    // 最も遠い頂点からさらに最も遠い頂点を見つける（直径の長さを求める）
    pair<int, int> farthest_from_farthest = dfs(farthest_from_start.second, -1);

    cout << farthest_from_farthest.first << endl; // 直径（最大距離）
    
    return 0;
}
0