結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, e) for (int i = (int)(s); i < (int)(e); ++i)
#define all(a) (a).begin(),(a).end()

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int N;
    cin >> N;
    vector<vector<pair<int, ll>>> G(N);
    rep(i, 0, N - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    
    vector<ll> dist(N);
    vector<bool> seen(N, false);
    queue<int> que;
    seen[0] = true;
    que.push(0);
    
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        
        for (pair<int, ll> e : G[v]) {
            if (seen[e.first]) continue;
            seen[e.first] = true;
            dist[e.first] = dist[v] + e.second;
            que.push(e.first);
        }
    }
    
    int s = 0;
    ll maxD = 0;
    rep(i, 0, N) {
        if (maxD < dist[i]) {
            maxD = dist[i];
            s = i;
        }
    }
    
    rep(i, 0, N) seen[i] = false;
    seen[s] = true;
    que.push(s);
    dist[s] = 0;
    
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        
        for (pair<int, ll> e : G[v]) {
            if (seen[e.first]) continue;
            seen[e.first] = true;
            dist[e.first] = dist[v] + e.second;
            que.push(e.first);
        }
    }
    
    ll ans = 0;
    rep(i, 0, N) ans = max(ans, dist[i]);
    
    cout << ans << '\n'; 
}
0