結果

問題 No.3113 The farthest point
コンテスト
ユーザー Facade
提出日時 2025-04-18 22:06:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,343 bytes
コンパイル時間 3,145 ms
コンパイル使用メモリ 286,252 KB
実行使用メモリ 19,648 KB
最終ジャッジ日時 2025-04-18 22:06:46
合計ジャッジ時間 9,078 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;cin>>n;
    vector<vector<pair<int,int>>>connect(n);
    for(int i=0;i<n-1;i++){
        int a,b,c;cin>>a>>b>>c;
        a--;b--;
        connect[a].push_back({b,c});
        connect[b].push_back({a,c});
    }
    //関数の返り値->遠い奴のコストも一緒に
    const int inf=1e18;
    auto BFS=[&](auto BFS,int start)->pair<int,int>{
        vector<bool>vis(n,false);
        vector<int>dist(n,inf);
        dist[start]=0;
        priority_queue<pair<int,int>>que;
        que.push({0,start});
        while(!que.empty()){
            auto[w,now]=que.top();
            que.pop();
            if(vis[now])continue;
            if(w>dist[now])continue;
            vis[now]=true;
            for(auto[to,ww]:connect[now]){
                if(!vis[to]){
                    if(dist[to]>dist[now]+ww){
                        dist[to]=dist[now]+ww;
                        que.push({dist[to],to});
                    }
                }
            }
        }
        int ret=0,ret2=0;
        for(int i=0;i<n;i++){
            if(ret2<dist[i]){
                ret2=dist[i];
                ret=i;
            }
        }
        return {ret,ret2};
    };
    auto[nxt,w]=BFS(BFS,0);
    auto[d,ans]=BFS(BFS,nxt);
    cout<<ans<<endl;
}
0