백준 1167 트리의 지름

www.acmicpc.net/problem/1167

1167번: 트리의 지름

이 문제도 1967번과 똑같은 문제다. 다만 입력받는 방식이 조금 귀찮아졌다.

 

마찬가지로 1번 노드에서 DFS를 돌리고 최댓값의 인덱스를 저장해 두었다가 다시 DFS를 돌리면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool vis[100001];
vector<pair<int, int>> ar[100001];
int ans, idx;

void dfs(int cur, int cost) {
	if (vis[cur]) return;
	vis[cur] = true;
	if (ans < cost) {
		ans = cost;
		idx = cur;
	}
	for (auto i : ar[cur]) {
		dfs(i.first, i.second + cost);
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, cost;
		cin >> x;
		while (1) {
			cin >> y;
			if (y == -1) break;
			cin >> cost;
			ar[x].push_back({ y,cost });
		}
	}
	dfs(1, 0);

	ans = 0;
	fill(vis, vis + 100001, false);

	dfs(idx, 0);
	cout << ans << endl;

	return 0;
}

다만 N의 범위가 10만이라 입출력에 조심해줘야 한다.