結果

問題 No.3113 The farthest point
ユーザー Facade
提出日時 2025-04-19 08:20:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,096 bytes
コンパイル時間 4,132 ms
コンパイル使用メモリ 289,028 KB
実行使用メモリ 19,824 KB
最終ジャッジ日時 2025-04-19 08:21:10
合計ジャッジ時間 9,693 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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});
    }
    vector<bool>vis(n,false);
    vis[0]=true;
    vector<int>dist(n,0);
    auto DFS=[&](auto DFS,int now)->int{
        int ret=0;
        for(auto[to,weight]:connect[now]){
            if(!vis[to]){
                vis[to]=true;
                ret=max(ret,DFS(DFS,to)+weight);
            }
        }
        dist[now]=ret;
        return ret;
    };
    DFS(DFS,0);
    vis.assign(n,false);
    int nn=0;
    vis[nn]=true;
    while (dist[nn]!=0){
        for(auto[to,weight]:connect[nn]){
            if(!vis[to]&& dist[to]==dist[nn]-weight){
                vis[to]=true;
                nn=to;
                break;
            }
        }
    }
    dist.assign(n,0);
    vis.assign(n,false);
    vis[nn]=true;
    DFS(DFS,nn);
    int ans=dist[nn];
    cout<<max(ans,(int)0)<<endl;
}
0