[백준 / BOJ] C++ 1753 최단경로

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

1753번: 최단경로

풀이

다익스트라 문제이다. 

시작노드부터 최단 경로를 찾아내며, 최단경로에 저장되어있는 가중치를 출력한다.

 

우선 아래 이미지는 위의 입력을 그림으로 표현하였다.

우선순위큐를 이용하여 가중치 낮은순으로 저장을 하고, 

해당 노드 방문시 시작지점으로부터 가중치를 더하여 비교를 하였을 때,

작은 경우만 출력을 해주면 된다.

 

Code ( C++ )

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000
#define NODE_MAX 20001
#define VERTEX_MAX 300001

using namespace std;

int V, E, K;
int minVal[NODE_MAX];

// pair <가중치, 도착노드>
vector<pair<int, int>> vec[VERTEX_MAX];
priority_queue<pair<int, int>> pq;

void Dijkstra(int idx)
{
	int NowIdx = 0;
	int weight = 0;
	// 자기 자신으로 가는 가중치는 없음.
	minVal[idx] = 0;

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

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

		pq.pop();

		if (minVal[NowIdx] < weight)
			continue;

		for (int i = 0; i < vec[NowIdx].size(); i++)
		{
			int next_node = vec[NowIdx][i].second;
			int total_weight = weight + vec[NowIdx][i].first;

			if (minVal[next_node] > total_weight)
			{
				minVal[next_node] = total_weight;

				pq.push(make_pair(-total_weight, next_node));
			}
		}
	}
}

int main()
{
	// 시작노드, 도착노드, 가중치
	int u, v, w;

	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> V >> E;
	cin >> K;

	fill(minVal, minVal + V + 1, INF);

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

		//시작노트 vec에 도착노드로 가는 가중치를 같이 저장
		vec[u].push_back(make_pair(w, v));
	}

	Dijkstra(K);

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