백준/1916번/최소비용 구하기/골드5

Problem Link: https://www.acmicpc.net/problem/1916

문제 설명

Site: Baekjoon
Number: 1916
Category: Dijkstra
Rank: Gold 5

여러 개의 도시에 한 도시에서 다른 도시로 도착하는 버스가 있다.

도시 A에서 도시 B까지 버스를 타고 갈때 최소비용을 구하라.

가중치가 있는 무방향 그래프에 다익스트라를 적용하면 바로 정답이 나오는 문제이다.

주어진 도시의 갯수와 버스의 갯수에 맞게 버스를 저장할 이중 배열과 한 도시에서 다른 도시들까지의 최단거리를 저장하는 배열을 만든다.

주어진 시작점에서 다익스트라를 통해 다른 도시들까지의 최단거리 배열을 저장하고 주어진 도착점까지의 최단거리를 출력한다.

#include <iostream>
#include <queue>

#define PII pair<int,int>
#define INF 2147483647

using namespace std;

// 우선순위 큐 pair<int, int> 정렬 기준용 구조체
struct cmp
{
	bool operator()(PII a, PII b)
	{
		return a.second > b.second;
	}
};

void Dijkstra(int n, vector<int>& dist, vector<vector<PII>>& v)
{
	priority_queue<PII, vector<PII>, cmp> pq;

	//시작 노드를 우선 순위 큐에 추가
	pq.push(PII(n, 0));

	while(!pq.empty())
	{
		//우선 순위 큐에 있는 연결된 노드 중 가중치가 가장 작은 노드를 가져온다
		int currentNode = pq.top().first;
		int currentDist = pq.top().second;
		pq.pop();

		//저장된 최단거리보다 크다면 무시한다
		if (dist[currentNode] < currentDist)
			continue;

		for(int i = 0; i < v[currentNode].size(); i++)
		{
			//가져온 노드와 연결된 노드를 가져온다
			int nextNode = v[currentNode][i].first;
			int nextNodeDist = v[currentNode][i].second + currentDist;

			//가져온 노드를 거쳐서 연결된 노드까지 가는 거리가 저장된 최단거리보다 작다면 큐에 넣고 최단거리를 갱신한다
			if (dist[nextNode] > nextNodeDist)
			{
				dist[nextNode] = nextNodeDist;
				pq.push(PII(nextNode, nextNodeDist));
			}
		}
	}
}

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

	int N, M;
	cin >> N >> M;

	//버스 저장 배열
	vector<vector<PII>> v(N + 1);

	//최단거리 저장 배열, 최단거리 비교를 위해 초깃값을 INF(최댓값)로 설정한다
	vector<int> dist(N + 1, INF);

	int start, dest, weight;
	for(int i = 0; i < M; i++)
	{
		cin >> start >> dest >> weight;
		v[start].emplace_back(dest, weight);
	}

	cin >> start >> dest;

	//시작점에서의 거리는 0
	dist[start] = 0;
	Dijkstra(start, dist, v);

	cout << dist[dest];

	return 0;
}