[c++/백준] 11779번: 최소비용 구하기 2

문제 링크

11779번: 최소비용 구하기 2

풀이

이전에 풀었던 최소비용 구하기와 같은 문제인데, 여기서 경로만 출력하면 되는 문제이다.
최소비용은 우선순위 큐를 이용해 거리가 짧은 것을 갱신시키는 다익스트라를 사용하면 된다.

다익스트라 과정은 위 링크의 풀이와 같으니 경로 출력만 보자면,

1. 2차원 벡터 route에는 각 index까지의 경로를 저장한다.
2. 비용이 갱신될 때마다 이전 도시의 route를 현재 도착하는 도시의 route에 넣고, 자기 자신도 넣는다.
3. 도착 도시의 route를 출력

⚠ 주의

버스의 비용이 100,000 이하이고, 도시의 개수는 1,000개이니까 최소 100,000,000은 넘어야한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000000

using namespace std;


int main()
{
	int n, m;
	int stt_city, arr_city;
	cin >> n >> m;

	vector<vector<pair<int,int>>> city(n+1); //인덱스 1~n

	for (int i = 0;i < m;i++)
	{
		int stt, arr, wei;
		cin >> stt >> arr >> wei;
		city[stt].push_back(make_pair(wei, arr));
	}

	cin >> stt_city >> arr_city;

	vector<int> dist(n+1, INF); //무한대로 거리 초기화
	vector<int> visit(n+1, 0);
	vector<vector<int>> route(n+1);
	priority_queue<pair<int, int>> pq;
	
	dist[stt_city] = 0;
	pq.push({ 0,stt_city });
	route[stt_city].push_back(stt_city);

	while (!pq.empty())
	{
		int cur = pq.top().second;
		pq.pop();
		if (visit[cur]==1) continue;
		visit[cur] = 1;

		for (auto u : city[cur])
		{
			int wei = u.first;
			int arr = u.second;
			if (dist[cur] + wei < dist[arr])
			{
				route[arr] = route[cur];
				route[arr].push_back(arr);
				dist[arr] = dist[cur] + wei;
				pq.push({ -dist[arr],arr });
			}
		}
	}
	
	cout << dist[arr_city] << endl;
	cout << route[arr_city].size()<<endl;
	for (int i = 0;i < route[arr_city].size();i++)
	{
		cout << route[arr_city][i] << " ";
	}
	cout << endl;


}

P.S.

이 문제는 예제 출력 경로가 1 3 5라고 했는데, 아마 이대로 풀면 1 4 5가 될거임
출력에 대해 별 조건이 없으니 맞았다고 뜰겁니다