골드3 - 백준 11779 최소비용 구하기 2

백준 11779 최소비용 구하기2

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

접근방법

이 문제는 단순하게 다익스트라 최단거리 알고리즘을 통해서 최단거리를 구하고, 직전 노드를 저장하여 백트래킹으로 경로를 구해준다.

풀이

linked 벡터를 이용해서 연결된 경로를 저장하고 cost배열에 걸리는 시간을 저장해준다. 저장할 때 중복된 경로가 들어올 수 있으므로 비교하여 최소값을 저장하도록 갱신해준다.
priority_queue를 이용하여 걸리는 시간이 짧은 순서대로 꺼내어서 목적지까지의 최소거리를 구해주고, 다익스트라를 진행하면서 visited에 저장되는 최소시간이 갱신될 때, past_node에 지나온 노드를 갱신해준다.
while문이 끝나면 back_tracking() 함수에서 경로를 result벡터에 저장해주고 거꾸로 출력해준다.

코드

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

using namespace std;

vector<vector<int>> linked;
int cost[1001][1001];
int visited[1001];
int past_node[1001];
vector<int> result;

void back_tracking(int node)
{
	result.push_back(node);
	while (true)
	{
		node = past_node[node];
		if (node == -1)
			break;
		result.push_back(node);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	memset(visited, -1, sizeof(visited));
	memset(past_node, -1, sizeof(past_node));
	memset(cost, -1, sizeof(cost));

	for (int i = 0; i <= N; i++)
	{
		vector<int> temp;
		linked.push_back(temp);
	}

	int start, end;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		linked[a].push_back(b);
		if(cost[a][b] == -1 || cost[a][b] > c)
			cost[a][b] = c;
	}

	cin >> start >> end;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,start });
	visited[start] = 0;

	while (!pq.empty())
	{
		int cur_cost = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		for (int i = 0; i < linked[cur_node].size(); i++)
		{
			if (visited[linked[cur_node][i]] == -1 || visited[linked[cur_node][i]] > cur_cost + cost[cur_node][linked[cur_node][i]])
			{
				visited[linked[cur_node][i]] = cur_cost + cost[cur_node][linked[cur_node][i]];
				past_node[linked[cur_node][i]] = cur_node;
				pq.push({ visited[linked[cur_node][i]], linked[cur_node][i] });
			}
		}
	}

	cout << visited[end] << '\n';
	back_tracking(end);
	cout << result.size() << '\n';
	for (int i = result.size()-1; i >= 0; i--)
		cout << result[i] << ' ';
	cout << '\n';

	return 0;
}