[백준 BOJ1753] 최단경로 (C++)

1. 제목

- 백준 1753 최단경로

- BOJ 1753 최단경로

문제 링크 : 1753번: 최단경로 (acmicpc.net)

1753번: 최단경로

---

2. 풀이 과정

 

풀이과정이랄 게 따로 없네요. 골드문제인데 다익스트라만 구현하면 그냥 바로 풀리는 문제예요. 다익스트라 개념만 알고 있으면 매우 쉽게 풀 수 있을 거 같아요.

 

[알고리즘] 다익스트라 (C++) :: 별빛상자 (tistory.com)

[알고리즘] 다익스트라 (C++)

---

3. 코드

#define INF 1000000000

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int V, E;
int startIndex;
vector <pair<int, int>> graph[20001];
int distances[20001];

void Dijkstra(int start)
{
	distances[start] = 0;
	priority_queue<pair<int, int>> pq;

	pq.push(make_pair(0, start));
	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int current = pq.top().second;
		pq.pop();
		
		//최단 거리가 아닌 경우 스킵
		if (distances[current] < distance) continue;

		for (int i = 0; i < graph[current].size(); i++)
		{
			// 선택된 노드를 인접 노드로 거쳐서 가는 비용
			int nextDistance = distance + graph[current][i].first;
			// 선택된 노드의 인접 노드
			int next = graph[current][i].second;
			// 기존의 최소 비용보다 더 저렴하다면 교체.
			if (nextDistance < distances[next])
			{
				distances[next] = nextDistance;
				pq.push(make_pair(-nextDistance, next));
			}
		}
	}
}

void Solution()
{
	for (int i = 1; i <= V; i++)
		distances[i] = INF;

	Dijkstra(startIndex);
	
	for (int i = 1; i <= V; i++)
	{
		if (distances[i] != INF)
			cout << distances[i] << "\n";
		else
			cout << "INF" << "\n";
	}
}


void Input()
{
	cin >> V >> E;

	cin >> startIndex;

	for (int i = 0; i < E; ++i)
	{
		int from;
		int to;
		int distance;
		cin >> from >> to >> distance;
		graph[from].push_back(make_pair(distance, to));
	}
}

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

	Input();
	Solution();

	return 0;
}