[C++] 백준 11779 : 최소비용 구하기 2

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

11779번: 최소비용 구하기 2

백준 11779번 최소비용 구하기 2 를 풀었다.

 

최대 도시의 개수가 1000개이고 간선에 음수 가중치가 없어서 다익스트라 알고리즘을 사용했다.

다익스트라 알고리즘에 최단 경로 출력을 합치면 된다.

경로를 저장하기 위해 path_temp 배열을 사용했다. 어느 도시에서 오는지 저장하는 배열이다.

index	1	2	3	4	5
value	0	1	1	1	4

예제의 경우 출발 도시가 1, 도착 도시가 5이다. 도착 도시부터 역으로 경로를 찾아가면 된다.

5에서 4, 4에서 1 이런 식으로 찾으면 1-4-5 라는 최단 경로를 구할 수 있다.

 

주의해야할 점은 출발 도시와 도착 도시가 똑같지만 비용이 다른 입력이 들어올 수 있다.

따로 처리를 해주지 않으면 시간 초과가 난다.

입력을 받을 때 처리하거나, 다익스트라 알고리즘에서 dist[현재노드]보다 현재노드의 비용이 클 경우 실행하지 않으면 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define INF 987654321
typedef pair<int, int> node; // end, cost
struct compare {
	bool operator()(node a, node b) {
		return a.second > b.second;
	}
};

int n, m;
int from, to;
vector<node> v[1001];
priority_queue<node, vector<node>, compare> pq;
vector<long long> dist;
int path_temp[1001];

void Dijkstra() {
	while (!pq.empty()) {
		int cur = pq.top().first;
		int cost = pq.top().second;
		pq.pop();
		if (dist[cur] < cost) continue;
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int next_cost = cost + v[cur][i].second;
			if (dist[next] > next_cost) {
				dist[next] = next_cost;
				path_temp[next] = cur;
				pq.push({ next,next_cost });
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		v[start].push_back({ end,cost });
	}
	cin >> from >> to;
	dist.assign(n + 1, INF);
	dist[from] = 0;
	pq.push({ from,dist[from] });
	Dijkstra();

	vector<int> path;
	int iter = to;
	path.push_back(iter);
	while (1) {
		if (iter == from)
			break;

		path.push_back(path_temp[iter]);
		iter = path_temp[iter];
	}

	cout << dist[to] << '\n';
	cout << path.size() << '\n';
	for (int i = path.size() - 1; i >= 0; i--)
		printf("%d ", path[i]);

	return 0;
}