노드 간의 가장 긴 거리를 구하는 문제이다. dfs를 사용했다. 먼저 경로들을 벡터에 양방향으로 저장을 해주고 노드의 갯수만큼 반복문을 돌려주었다. dfs
함수에서 경로를 따라 sum
을 구해 res
와 비교 후 더 큰 값을 저장해주었다. 최종적으로 모든 노드를 돌게되면서 가장 큰 값이 저장되게되고 이를 출력하였다.
간선을 저장하는 아이디어는 이전에 다익스트라 문제를 풀 때 이용했던 방식을 사용했다. 시간 초과가 날 줄 알았는데 바로 통과해서 빠르게 풀 수 있었다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n, res = 0;
bool check[10001];
vector<pair<int, int>> v[10001];
void dfs(int depth, int cur, int sum) {
res = max(res, sum);
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i].first;
int cost = v[cur][i].second;
if (check[next]) continue;
check[next] = true;
dfs(depth + 1, next, sum + cost);
}
}
void solution() {
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
check[i] = true;
dfs(0, i, 0);
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
v[b].push_back({ a,c });
}
solution();
return 0;
}