BaekJoon 11779번: 최소비용 구하기 2(C++)

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

11779번: 최소비용 구하기 2

풀이법

1) m개의 반복을 통해 들어갈 값들은 단방향 그래프임을 잊지 말자

2) a에서 b까지 가는 버스의 값이 여러 개 주어질 수도 있다. (min 함수를 활용하여 더 적은 것을 입력 값으로 활용하는 것을 배제하면 7%쯤에서 error가 발생한다.)

3) 다익스트라 알고리즘을 활용하여 최소 비용을 구해야 하는 문제이다. 기존의 다익스트라 문제와 달리 경로를 구해야 하므로 visited 배열을 활용하여 어떤 곳을 거쳤는지를 확인하는 작업이 중요하다.

 

#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;

int arr[1001][1001];
int tempAns[1001];
int visited[1001];
int n, m;
int startNode, endNode;
void dijk()
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
	for (int i = 1; i <= n; i++)
		tempAns[i] = INF;
	tempAns[startNode] = 0;
	pq.push({ 0,startNode });
	while (!pq.empty())
	{
		int cost = pq.top().first;
		int curIndex = pq.top().second;
		pq.pop();
		if (tempAns[curIndex] < cost)
			continue;
		for (int i = 1; i <= n; i++)
		{
			if (arr[curIndex][i] == INF)
				continue;
			int nextCost = cost + arr[curIndex][i];
			if (nextCost < tempAns[i])
			{
				tempAns[i] = nextCost;
				visited[i] = curIndex;
				pq.push({ nextCost,i });
			}
		}
	}
	cout << tempAns[endNode] << "\n";
	vector<int> ans;

	int temp = endNode;
	while (temp)
	{
		ans.push_back(temp);
		temp = visited[temp];
	}
	cout << ans.size() << "\n";
	for (int i = ans.size() - 1; i >= 0; i--)
	{
		cout << ans[i] << " ";
	}
	cout << "\n";
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			arr[i][j] = INF;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (arr[a][b] != INF)
			arr[a][b] = min(arr[a][b], c);
		else
			arr[a][b] = c;
	}
	cin >> startNode >> endNode;
	dijk();
}