[백준/BOJ] 백준 1753번 : 최단경로

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

1753번: 최단경로

시작 정점으로부터 각 정점으로 최단 경로를 구하는 방법은 다익스트라 알고리즘을 사용하였다. 우선순위 큐에 -(지금까지 구한 최단경로), 목적지 순서로 저장하여서 지금까지 구한 최단경로가 짧은 것이 먼저 우선순위 큐에서 나오도록 하였다.

 

코드

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

int V, E;

vector<pair<int, int>> adj[20000]; //pair:가중치, 목적지 순서로 저장

// start정점으로부터 각 정점으로의 최단 경로 경로 값을 출력한다
void Solve(int start)
{
	//각 정점으로의 최단경로의 경로값을 저장
	//매우 큰 수로 987654321로 초기화
	vector<int> result(V,987654321);

	//pair:-(지금까지 구한 최단경로),목적지 순서로 저장
	//-(지금까지 구한 최단경로) 저장하는 이유는 지금까지 구한 최단경로가 작은것 부터 뽑기 위해서
	priority_queue<pair<int, int>> pq;

	//자신의 위치까지 가는 최단 경로는 0
	result[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		//here위치에 더 짧은 최단경로로 이미 갱신되었을때
		if (result[here] < here_cost)
			continue;

		//here에 인접한 간선들을 확인한다
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = adj[here][i].first + here_cost;

			//there위치까지 가는 더 짧은 최단 경로를 발견 했을때
			if (result[there] > there_cost)
			{
				//업데이트
				result[there] = there_cost;

				//우선순위 큐에 저장
				pq.push(make_pair(-there_cost, there));
			}
		}

	}

	for (int i = 0; i < result.size(); i++)
	{
		//처음에 초기화한 값에서 변경이 없는 경우는 경로가 존재하지 않는것이다
		if (result[i] == 987654321)
			cout << "INF" << "\n";

		else
			cout << result[i] << "\n";
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int k;
	int u, v, w;

	cin >> V >> E;
	cin >> k;

	for (int i = 0; i < E; i++)
	{
		cin >> u >> v >> w;

		//정점의 번호를 0부터 매기기 위해 u와 v에 -1을 하였다
		adj[u-1].push_back(make_pair(w, v-1));
	}
	
	//정점의 번호를 0부터 매겼으므로 k-1정점으로부터 각 정점으로의 최단 경로 경로 값을 출력한다
	Solve(k-1);

	return 0;
}