結果

問題 No.3113 The farthest point
コンテスト
ユーザー Hoang Nho Dinh
提出日時 2025-04-19 01:18:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,263 bytes
コンパイル時間 2,190 ms
コンパイル使用メモリ 197,024 KB
実行使用メモリ 20,296 KB
最終ジャッジ日時 2025-04-19 01:18:09
合計ジャッジ時間 6,369 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
const int nxm = 2e5 + 10;
int n;
vector<pair<int, long long >> g[nxm];
long long dist[nxm];
bool visited[nxm];
void findLongestPath(int u) {
	visited[u] = true;
	for (auto [v, w] : g[u]) {
		if (!visited[v]) {
			dist[v] = dist[u] + w;
			findLongestPath(v);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		long long w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = -1e18;
	}
	int firstLongest = 1;
	dist[1] = 0;
	findLongestPath(1);
	for (int i = 1; i <= n; i++) {
		if (dist[i] > dist[firstLongest]) {
			firstLongest = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = -1e18;
	}
	memset(visited, 0, sizeof(visited));
	dist[firstLongest] = 0;
	findLongestPath(firstLongest);
	int secondLongest = 1;
	for (int i = 1; i <= n; i++) {
		if (dist[i] > dist[secondLongest]) {
			secondLongest = i;
		}
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = -1e18;
	}
	memset(visited, 0, sizeof(visited));
	int ans = 1;
	findLongestPath(secondLongest);
	for (int i = 1; i <= n; i++) {
		if (dist[i] > dist[ans]) {
			ans = i;
		}
	}
	cout << dist[ans] << '\n';
	return 0;
}
0