문제 링크: https://www.acmicpc.net/problem/1967
dfs 2번에 깔끔하게 풀리는 문제입니다. 풀이는 요기로
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> graph[10000]; // idx, cost (root=0)
bool visited[10000];
int max_len;
int max_idx;
void dfs(int idx, int len) {
if (max_len < len) {
max_len = len;
max_idx = idx;
}
for (auto& [next, nextDist] : graph[idx]) {
if (!visited[next]) {
visited[next] = true;
dfs(next, len + nextDist);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int a, b, c;
cin >> a >> b >> c;
--a, --b;
graph[a].emplace_back(b, c);
graph[b].emplace_back(a, c);
}
dfs(0, 0);
memset(visited, 0, sizeof(visited));
dfs(max_idx, 0);
cout << max_len << '\n';
return 0;
}
반응형
'Online Judge > 백준' 카테고리의 다른 글
[백준][C++] 10707: 수도요금 (0) | 2020.07.16 |
---|---|
[백준][C++] 10173: 니모를 찾아서 (0) | 2020.07.15 |
[백준][C++] 1520: 내리막 길 (0) | 2020.07.14 |
[백준][C++] 19230: Datum (0) | 2020.07.14 |
[백준][C++] 19235: 모노미노도미노 (4) | 2020.07.13 |