結果

問題 No.3113 The farthest point
ユーザー ako yas
提出日時 2025-04-19 21:12:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,438 bytes
コンパイル時間 1,229 ms
コンパイル使用メモリ 103,788 KB
実行使用メモリ 18,128 KB
最終ジャッジ日時 2025-04-19 21:12:10
合計ジャッジ時間 4,827 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility> // std::pairのため
#include <climits> // LLONG_MINのため (long long の最小値)
#include <algorithm> // std::max のため (必須ではないが便利)

// long long 型を頻繁に使うためエイリアスを設定
using ll = long long;
// std::pair<int, ll> を短く書くためのエイリアス (任意)
using Edge = std::pair<int, ll>;

// グラフの隣接リスト表現 (ノード番号: {隣接ノード, 重み} のリスト)
std::vector<std::vector<Edge>> adj;

// DFSの結果を格納するための変数 (グローバル変数として定義)
ll current_max_dist;       // 現在のDFS実行で見つかった最大距離
int current_farthest_node; // 現在のDFS実行で見つかった最も遠いノード

// 深さ優先探索 (Depth First Search)
// u: 現在のノード
// p: 親ノード (逆戻り防止用)
// dist_u: DFS開始ノードから現在のノードuまでの距離
void dfs(int u, int p, ll dist_u) {
    // 現在のノードまでの距離が、これまでの最大距離より大きいかチェック
    if (dist_u > current_max_dist) {
        current_max_dist = dist_u;
        current_farthest_node = u;
    }

    // 隣接ノードを探索
    // adj[u] に格納されている各要素 (辺) についてループ
    for (const Edge& edge : adj[u]) {
        int v = edge.first;  // 隣接ノード番号
        ll weight = edge.second; // 辺の重み

        // 親ノードでなければ再帰的に探索
        if (v != p) {
            dfs(v, u, dist_u + weight); // 距離を更新して再帰呼び出し
        }
    }
}

int main() {
    // 高速な入出力設定 (任意だが、大量の入出力がある場合に推奨)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // 頂点の数
    std::cin >> n;

    // --- エッジケース: 頂点が1つの場合 ---
    if (n == 1) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // --- グラフの構築 ---
    adj.resize(n + 1); // 頂点番号1からnまで使うため、サイズを n+1 にする

    // 辺の情報を読み込み、隣接リストを作成 (n-1本の辺)
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        ll w; // 重みは long long で受け取る
        std::cin >> u >> v >> w;
        // 無向グラフなので、両方向に追加
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // --- 1回目のDFS ---
    // 任意の頂点 (ここでは頂点1) から開始
    current_max_dist = -1; // or LLONG_MIN; 距離は0以上なので-1でも可だが、負重み考慮ならLLONG_MIN
    current_farthest_node = 1; // 開始ノードを初期値とする
    dfs(1, -1, 0); // 頂点1から、親なし(-1)、初期距離0でDFS開始

    // 1回目のDFSの結果、最も遠かった頂点が current_farthest_node (これを u とする) に格納される
    int u = current_farthest_node;

    // --- 2回目のDFS ---
    // 頂点 u から開始
    current_max_dist = -1; // or LLONG_MIN; 再度初期化
    current_farthest_node = u; // 開始ノードをuとする
    dfs(u, -1, 0); // 頂点uから、親なし(-1)、初期距離0でDFS開始

    // 2回目のDFSの結果、current_max_dist に格納された値が木の直径となる
    std::cout << current_max_dist << std::endl;

    return 0;
}
0