백준 11779 최소비용 구하기 2

1. 문제 링크

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

11779번: 최소비용 구하기 2

 

2.  풀이

전형적인 최단거리 문제이다.

다만 최소비용을 갖는 경로를 출력하는 부분이 추가되었다.

이 부분은 각 정점마다 최소 비용이 결정되는 시점에, 해당 정점으로 오기 바로 직전 정점을 별도의 배열에 표시해 둠으로 서 해결했다.

//n(1≤n≤1,000)개의 도시 => 정점
//m(1≤m≤100,000)개의 버스 => 간선

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class Element {
public:
	int vertex, weight, prev;
	Element() {};
	Element(int vertex, int weight, int prev) {
		this->vertex = vertex;
		this->weight = weight;
		this->prev = prev;
	};
};

struct compare {
	bool operator()(const Element& e1, const Element& e2) {
		return e1.weight > e2.weight;
	}
};

const int			INTMAX = 2000000000;
int					N, M;
vector<Element>		graph[1001];
int					dist[1001];
bool				visited[1001];
int					prevVertex[1001];
int					start, dest;

void InputAndInit() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		graph[i].clear();
		dist[i] = INTMAX;
		visited[i] = false;
		prevVertex[i] = -1;
	}
	int t1, t2, t3;
	for (int i = 0; i < M; i++) {
		cin >> t1 >> t2 >> t3;
		graph[t1].push_back({ t2,t3, -1 });
	}

	cin >> start >> dest;
}

int main() {
	InputAndInit();
	priority_queue<Element, vector<Element>, compare> pq;
	dist[start] = 0;
	pq.push({ start,0 ,start});
	while (!pq.empty()) {
		Element currentE = pq.top(); pq.pop();
		if (visited[currentE.vertex])
			continue;

		visited[currentE.vertex] = true;
		prevVertex[currentE.vertex] = currentE.prev;
		if (currentE.vertex == dest)
			break;
		for (Element nextE : graph[currentE.vertex]) {
			if (visited[nextE.vertex])
				continue;
			if (dist[nextE.vertex] > dist[currentE.vertex] + nextE.weight) {
				dist[nextE.vertex] = dist[currentE.vertex] + nextE.weight;
				pq.push({ nextE.vertex, dist[currentE.vertex] + nextE.weight, currentE.vertex });
			}
		}
	}

	cout << dist[dest] << "\n";
	vector<int> tmp;
	tmp.push_back(dest);
	int idx = dest;
	while (idx != start) {
		idx = prevVertex[idx];
		tmp.push_back(idx);
	}

	cout << tmp.size() << "\n";
	for (auto iter = tmp.rbegin(); iter != tmp.rend(); iter++)
		cout << *iter << " ";
	cout << "\n";
	return 0;
}