1753번: 최단경로 (BOJ C/C++)

1753번: 최단경로

사용 언어: C++

 

풀이

//우선 순위 큐를 이용한 다익스트라 알고리즘으로 최단경로 구하기

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1e9

int v, e, start; //V: 정점의 개수, E: 간선의 개수, start: 시작 정점의 위치

vector<pair<int, int>> arr[20001]; //각 노드가 연결된 노드 정보 저장
//1번째 노드가 3번째 노드에 연결되어있다를 표현하려면 arr[1] <3, 거리>

int dist[20001]; //최단 거리 정보 저장

void dijkstra(int start)
{
	priority_queue<pair<int,int>> pq; //<거리, 인덱스>
	pq.push({0,start});
	dist[start] = 0;

	while(!pq.empty())
	{
		int dist2 = -pq.top().first; //-붙인 이유: 최소 비용 꺼낼때 -붙어있어서 다시 -
		//dist : 현재 노드까지의 거리
		int cur = pq.top().second; //현재 노드
		pq.pop();

		for(int i=0; i<arr[cur].size(); i++)
		{
			int next = arr[cur][i].first; //다음 노드
			int nextdist = arr[cur][i].second; //다음 노드까지의 거리
			int cost  = dist2 + nextdist; //cost: 현재 거리 + 다음 노드까지의 거리

			if(cost < dist[next])
			{
				dist[next] = cost; //더 짧은 거리로 갈 수 있으므로 갱신
				pq.push({-cost, next}); //여기서 -를 붙여야 꺼낼때 최소 비용을 꺼냄
			}
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> v >> e >> start;

	for(int i=0; i<e; i++)
	{
		int x,y,z;
		cin >> x >> y >> z; //x번 노드에서 y번 노드로 가는 비용이 z
		arr[x].push_back({y,z});
	}

	fill(dist, dist + 20001, INF);

	dijkstra(start);

	for(int i=1; i<=v; i++)
	{
		if(dist[i] == INF)
			cout << "INF" << '\n';
		else
			cout << dist[i] << '\n';
	}

	return 0;
}