백준 : 1753번 최단경로 다익스트라 (c++)

백준 링크

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

1753번: 최단경로

코드 풀이

• 입력에서 주어진 방향 그래프 노드 연결
• 다익스트라는 최소 가중치값을 구하는것이기 때문에 Dist 배열을 INTMAX값으로 전부 초기화
• 시작노드를 기준으로한 다익스트라 시작
• 다익스트라 종료후 Dist배열을 순회하며 각 노드의 최소 가중치값을 출력, INTMAX라면 INF 출력

코드

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

using namespace std;

#define MAX 20001
#define INTMAX 2147483647

int V, E, K;

vector<pair<int, int>> Graph[MAX];
vector<int> Dist;

void Dijkstra(int StartNode)
{
	// Dist배열 resize
	Dist.resize(V + 1);
	fill(Dist.begin(), Dist.begin() + V + 1, INTMAX);

	// 실질적 다익스트라 시작점
	// 우선순위 큐 생성
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	// Cost, Node순으로저장(우선순위 큐에 pair로 저장할 경우 first값에 의해 정렬이 되기 때문)
	pq.push({ 0, StartNode });
	// 시작노드 거리 초기화 = 0
	Dist[StartNode] = 0;

	// 큐가 빌때까지 실행
	while (!pq.empty())
	{
		// 현재의 노드와 가중치 얻어옴
		int CurNode = pq.top().second;
		int CurCost = pq.top().first;
		// 얻어왔기 때문에 제거(제거 안 하면 무한루프)
		pq.pop();

		// 현재 노드까지의 가중치값이(이전에 지나온 모든 가중치를 더한 값이라 생각)
		// Dist에 저장되어있는 CurNode 인덱스의 Value값보다 크다면 실행할 필요 없음
		// 최소값을 구해야 하기 때문
		if (Dist[CurNode] < CurCost)
			continue;

		// 현재 노드에 연결되어있는 노드의 개수만큼 for문
		size_t Size = Graph[CurNode].size();
		for (size_t i = 0; i < Size; ++i)
		{
			// 다음 노드와 다음 노드까지의 가중치 값을 구한다.
			int NextNode = Graph[CurNode][i].first;
			int NextCost = Graph[CurNode][i].second + CurCost;

			// 다음 노드까지의 가중치 값이 현재 저장되어있는 Dist[NextNode]보다 값이 작다면
			// 갱신해줘야한다.
			if (Dist[NextNode] > NextCost)
			{
				pq.push({ NextCost, NextNode });
				Dist[NextNode] = NextCost;
			}
		}
	}
}

int main()
{
	cin >> V >> E;
	cin >> K;

	// 그래프 연결
	for (int i = 0; i < E; ++i)
	{
		int NodeU, NodeV, CostW;
		cin >> NodeU >> NodeV >> CostW;
		Graph[NodeU].push_back({ NodeV, CostW });
	}

	Dijkstra(K);

	// 각 노드 돌면서 값 출력
	for (int i = 1; i <= V; ++i)
	{
		if (Dist[i] != INTMAX)
		{
			cout << Dist[i] << '\n';
		}
		else
		{
			cout << "INF" << '\n';
		}
	}

	return 0;
}