結果

問題 No.3113 The farthest point
ユーザー kq5y
提出日時 2025-04-19 16:09:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,140 bytes
コンパイル時間 1,403 ms
コンパイル使用メモリ 112,380 KB
実行使用メモリ 20,088 KB
最終ジャッジ日時 2025-04-19 16:09:15
合計ジャッジ時間 8,186 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

# define int long long
using namespace std;

int n;
vector<vector<pair<int, int>>> graph;

pair<int, int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (auto [neighbor, weight] : graph[node]) {
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[node] + weight;
                q.push(neighbor);
            }
        }
    }

    int max_dist = 0, farthest_node = start;
    for (int i = 1; i <= n; ++i) {
        if (dist[i] > max_dist) {
            max_dist = dist[i];
            farthest_node = i;
        }
    }

    return {farthest_node, max_dist};
}

signed main() {
    cin >> n;
    graph.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    auto [u, dist1] = bfs(1);
    auto [v, diameter] = bfs(u);

    cout << diameter << endl;

    return 0;
}
0