[백준 1967] 트리의 지름 (C++)

문제 링크: https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

1. 주의할 점

- 간선에 대한 정보를 배열이 아닌 List 형태인 V[] 벡터에 저장한다

- 다익스트라를 2번 구현한다

 

2. 구현

- 모든 간선에 대한 정보를 V[] 벡터에 저장한다

- Dijsktra 알고리즘을 통해 Root Node에서 가장 길이가 먼 Node를 구한다

- 위에 구한 Node에서 시작하여 Dijsktra를 다시 수행하며 가장 긴 트리의 지름을 구한다

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
vector<info> v[10001];
int dist[10001];
int node, s, e, val, maxi = 0, midx;

void dijkstra(int start) {
	for (int i = 1; i <= node; i++)
		dist[i] = -1;
	queue<info> q;
	tmp.idx = start;
	tmp.val = 0;
	q.push(tmp);
	dist[start] = 0;
	while (!q.empty()) {
		int cidx = q.front().idx;
		int cv = q.front().val;
		q.pop();
		if (cv > maxi) {
			maxi = cv;
			midx = cidx;
		}
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i].idx;
			if (dist[next] != -1) continue;
			int nv = v[cidx][i].val;
			dist[next] = nv + cv;
			tmp.idx = next;
			tmp.val = nv + cv;
			q.push(tmp);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node;
	for (int i = 0; i < node - 1; i++) {
		cin >> s >> e >> val;
		tmp.idx = e;
		tmp.val = val;
		v[s].push_back(tmp);
		tmp.idx = s;
		v[e].push_back(tmp);
	}
	dijkstra(1);
	maxi = 0;
	dijkstra(midx);
	cout << maxi;
	return 0;
}