[C++] 백준 1753번 최단경로

방향그래프에서 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다.

우선순위 큐를 이용해서 시작점부터 연결된 선들에 대해
가중치가 낮은 선들을 먼저 탐색합니다.
그리고 각 정점에 대한 거리를 갱신해줍니다.

이를 반복하여 우선순위 큐에 값이 없을때 까지 실행하며,
최종적으로 저장되어있는 각 정점에 대한 거리를 출력해줍니다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int INF = 987654321;
int vertex, edge;
int start;
int u, v, w;
vector< pair<int, int> > map[20010];
priority_queue<pair <int, int> > pq;

vector<int> solve()
{
	int location;
	int weight;
	int nextLocation;
	int nextWeight;
	vector<int> result(vertex, INF);

	result[start] = 0;

	pq.push(make_pair(0, start));

	while (!pq.empty()) {
		weight = -pq.top().first;
		location = pq.top().second;

		pq.pop();

		if (result[location] < weight) {
			continue;
		}

		for (int i = 0; i < map[location].size(); ++i) {
			nextLocation = map[location][i].first;
			nextWeight = weight + map[location][i].second;

			if (result[nextLocation] > nextWeight) {
				result[nextLocation] = nextWeight;
				pq.push(make_pair(-nextWeight, nextLocation));
			}
		}
	}

	return result;
}

int main(int argc, char *argv[])
{
	scanf("%d", &vertex);
	scanf("%d", &edge);
	scanf("%d", &start);

	vertex++;

	for (int i = 1; i <= edge; ++i) {
		scanf("%d", &u);
		scanf("%d", &v);
		scanf("%d", &w);

		map[u].push_back(make_pair(v, w));
	}

	vector<int> result = solve();

	for (int i = 1; i < vertex; ++i) {
		result[i] == INF ? printf("INF\n") : printf("%d\n", result[i]);
	}

	return 0;
}