11779 최소비용 구하기 2

이 문제는 처음에 플로이드로 풀려했으나, 접근이 틀렸다. 왜냐하면 플로이드는 O(V^3)이기 때문에 정점이 최대 1000개 이면 당연히 시간초과가 난다..

따라서 O(VlgE)의 시간복잡도를 갖는 다익스트라를 사용하여 접근해야 한다.

일반적인 다익스트라는 최소비용을 구하는 로직이 대부분이지만 문제에서는 경로도 출력하는걸 요구하고 있다.

다익스트라에서 경로를 출력하기 위해서는 다음 vertex로 가는 최단경로를 업데이트할 때 기록해두고 역추적 방식으로 구현할 수 있다!

정답 코드에선 path라는 vector 타입으로 사용하였다.

 

정답코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#define INF 987654321
#define MAX_V 1001
using namespace std;
int N, M;
int Start, End;
vector<pair<int, int>> adj[MAX_V];

void djikstra(int start)
{
	vector<int> dist(N + 1, INF);
	vector<int> path(N + 1, INF);
	dist[start] = 0;
	path[start] = 0;

	priority_queue < pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;
	pq.push({ start, 0 });
	while (!pq.empty()) {
		int here = pq.top().first;
		int cost = pq.top().second;
		pq.pop();

		if (dist[here] < cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++){
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;
			if (dist[there] > nextDist) {
				dist[there] = nextDist;
				//다음 vertex 경로를 업데이트
				path[there] = here;
				pq.push({ there, nextDist });
			}
		}
	}
	int vertex = End;
	vector<int> trace;
	while (path[vertex]) {
		trace.push_back(vertex);
		vertex = path[vertex];
	}
	trace.push_back(start);
	printf("%d\n%d\n", dist[End], trace.size());
	for (int i = trace.size() - 1; i >= 0; i--) {
		printf("%d ", trace[i]);
	}
}
int main()
{
	cin >> N >> M;
	int s, e, d;
	for (int i = 0; i < M; i++) {
		cin >> s >> e >> d;
		adj[s].push_back({ e, d });
	}
	cin >> Start >> End;
	djikstra(Start);
	return 0;
}