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

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

11779번: 최소비용 구하기 2

---

풀이

출발~도착도시까지의 최소 비용은 다익스트라 알고리즘을 이용해 구했다. 

현재 저장된 비용은 다른 노드들에 의해 갱신되므로 큐에 저장된 비용보다 작을 수 있다.이런 경우는 실행하지 않아야 시간초과가 나지 않는다..

 

이 때, 해당 도시의 직전 도시를 같이 저장해서 경로를 저장했다.경로는 도착도시부터 시작해서 거슬러 올라갔으며, 출발 도시의 직전 도시는 출발 도시의 값으로 저장해두어 현재 도시!=직전도시일 때까지 올라가며 저장 후 출력했다.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <climits>
using namespace std;

vector <pair<int, int>> V[1001];
vector <int> S;
int Price[1001][2]; // 최소 비용과, 버스가 온 도시 저장
bool visited[1001];

void Bus(int start, int end) {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;

	// 출발 도시까지의 비용은 0, 출발도시의 이전 도시는 출발도시와 동일
	Price[start][0] = 0, Price[start][1] = start;
	pq.push({ Price[start][0], start });
	
	// 각 도시까지 가는 최소 비용 구하기
	while (!pq.empty()) {
		int now = pq.top().second, now_price = pq.top().first;
		pq.pop();
		visited[now] = true;

		// 현재까지의 최소비용이 큐에 저장된 값보다 적다면 실행 x , 없으면 시간초과ㅠ
		if (Price[now][0] < now_price) continue;

		for (int i = 0; i < V[now].size();i++) {
			int next = V[now][i].first, next_price = V[now][i].second;
		
			if (visited[next]) continue;

			if (Price[next][0] > now_price + next_price) {
				Price[next][0] = now_price + next_price;
				
				// 경로가 갱신될 때 어느 도시에서 왔는지 저장
				Price[next][1] = now;
				pq.push({ Price[next][0], next }); 
			}
		}
	}

	// 최소 비용을 갖는 경로 구하기
	int before = end;
	while (1) {
		if (before == Price[before][1]) break; // 출발도시일 때
		S.push_back(before);
		
		// 해당 도시 전에 왔던 도시로 이동
		before = Price[before][1];
	}
	S.push_back(start);

	// print
	printf("%d\n%d\n", Price[end][0], S.size());
	for (int i = S.size() - 1; i >= 0; i--) printf("%d ", S[i]);
}
int main() {
	int n, m;
	int start, end, cost;

	// input
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &start, &end, &cost);
		V[start].push_back({ end, cost });
	}
	scanf("%d %d", &start, &end);

	fill(Price[1], Price[n + 1], INT_MAX);
	Bus(start, end);

	return 0;
}