백준 1967번 C++ 풀이

문제

https://www.acmicpc.net/problem/1967

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 4

---

풀이

https://codejin.tistory.com/294

백준 1167번 C++ 풀이

이 문제를 풀던 도중 쏟아져내리는 MLE에 정신을 못차리고 트리의 지름 문제를 백준에 검색했다가 나온 문제이다. 1167번에 비해 n이 10배 적고, 입력도 매우 착한 문제라고 할 수 있다. 풀이는 위의 1167번을 참조하자. 입력부분을 제외하면 같은 코드이다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> graph;
int answer = -1;

void input() {
	int st, dest, dist, n;
	cin >> n;
	graph.resize(n + 1);

	while(--n) {
		cin >> st >> dest >> dist;
		graph[st].push_back({dest, dist});
	}
}

void update(pair<int, int>& p, int val) {
	auto& [m1, m2] = p;
	if (val >= m1) {
		m2 = m1;
		m1 = val;
	}
	else if (val > m2) {
		m2 = val;
	}
}

int max_length(int cur, int parent) {
	pair<int, int> length = {0,0};

	for(auto& [child, dist] : graph[cur]) {
		if (child == parent) {
			continue;
		}
		update(length, dist + max_length(child, cur));
	}
	answer = max(answer, length.first + length.second);
	return length.first;
}

void sol() {
	max_length(1, -1);
	cout << answer;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}