結果

問題 No.3113 The farthest point
コンテスト
ユーザー moti
提出日時 2025-04-19 06:33:20
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,197 bytes
コンパイル時間 1,060 ms
コンパイル使用メモリ 136,720 KB
実行使用メモリ 20,292 KB
最終ジャッジ日時 2025-04-19 06:33:30
合計ジャッジ時間 7,588 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

#define MAX_V 200010
#define INF 1e17

typedef long long ll;

struct Edge {
    int to; ll cost;
    Edge(int to, ll cost) : to(to), cost(cost) {}
};

int V; ll maxi; int start;
ll dist[MAX_V];
bool visited[MAX_V];
vector<Edge> G[MAX_V];

void getStart(int v, ll d)
{
    if (dist[v] < INF) return;
    dist[v] = d;
    if (maxi < d) {
        maxi = d; start = v;
    }
    for (int i = 0; i < (int)G[v].size(); i++) {
	Edge e = G[v][i];
	getStart(e.to, d+e.cost);
    }
}

ll getTreeDiameter(int v)
{
    ll res = 0;
    for (int i = 0; i < (int)G[v].size(); i++) {
	Edge e = G[v][i];
	if (!visited[e.to]) {
	    visited[e.to] = true;
	    res = max(res, e.cost+getTreeDiameter(e.to));
	}
    }
    return res;
}

int main()
{
  int a, b; ll w;
  cin >> V;
  for (int i = 0; i < V-1; i++) {
    cin >> a >> b >> w;
    a--; b--;
    G[a].push_back(Edge(b, w));
    G[b].push_back(Edge(a, w));
  }
  maxi = 0; fill(dist, dist+V, INF);
  getStart(0, 0);
  memset(visited, false, sizeof(visited));
  visited[start] = true;
  cout << getTreeDiameter(start) << endl;
  return 0;
}
0