[C++] 백준 1167 : 트리의 지름

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

1167번: 트리의 지름

백준 1167번 트리의 지름을 풀었다.

 

다익스트라를 두 번 사용해서 문제를 풀었다.

편의상 첫 번째 다익스트라는 1번 노드에서 시작하는 것으로 설정했다.

첫 번째 다익스트라를 실행하고 나면 1번 노드에서 가장 멀리 있는 노드를 리턴 값으로 넘겨주게 된다.

리턴되는 노드에서 다시 다익스트라를 실행하면 다시 그 노드로부터 가장 멀리 있는 노드를 넘겨준다.

넘겨준 노드와의 거리가 트리의 지름이 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#pragma warning(disable:4996)

using namespace std;
#define INF 1234567890

struct Node {
	int end;
	int cost;
	Node() {}
	Node(int X,int Y) : end(X), cost(Y) {}
};
struct compare {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

vector<Node> vertex[100001];
int n;

Node Dijkstra(int n,int x) {
	priority_queue < Node, vector<Node>, compare> pq;
	vector<long long> dist;
	Node temp;
	int farthest_node = 0;
	int farthest_dist = 0;
	dist.assign(n + 1, INF);
	dist[x] = 0;
	temp.end = x;
	temp.cost = dist[x];
	pq.push(temp);

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		int cost = temp.cost;
		pq.pop();

		for (int i = 0; i < vertex[cur].size(); i++) {
			temp = vertex[cur][i];
			int next = temp.end;
			int next_cost = cost + temp.cost;
			if (dist[next] > next_cost) {
				dist[next] = next_cost;
				pq.push(Node(next, next_cost));

				if (farthest_dist < next_cost) {
					farthest_dist = next_cost;
					farthest_node = next;
				}
			}
		}
	}

	return Node(farthest_node,farthest_dist);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int start, end, cost;
		cin >> start;
		while (1) {
			Node temp;
			cin >> end;
			if (end == -1)
				break;
			cin >> cost;

			temp.end = end;
			temp.cost = cost;
			vertex[start].push_back(temp);
		}
	}

	Node temp;
	temp = Dijkstra(n, 1);

	temp = Dijkstra(n, temp.end);

	cout << temp.cost;

	return 0;
}