[백준/BOJ] 백준 11779번 : 최소비용 구하기 2

www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

다익스트라 알고리즘을 이용하여 start부터 dest까지 가는데 최소비용을 구하고, int come_from[1001];를 이용해 해당 지점에 올 때 어느 지점에서 왔는지 저장해서 경로를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<pair<int, int>> adj[1001]; //pair는 비용, 도착지 순서이다
int come_from[1001]; //경로를 구할때 사용할것으로, 어느 지점에서 왔는지 저장한다
vector<int> path;

void pathFind(int here)
{
	//here가 출발지점일때
	if (come_from[here] == -1)
	{
		path.push_back(here);

		//도착지부터 출발지까지 경로이므로 거꾸로 뒤집어서 출발지부터 도착지까지 경로로 바꾼다
		reverse(path.begin(), path.end());

		return;
	}

	path.push_back(here);

	pathFind(come_from[here]);
}

int Solve(int start, int dest)
{
	vector<int> short_dest(n + 1, 987654321);
	priority_queue<pair<int, int>> pq; //pair에 비용 ,도착지 순서로 저장

	short_dest[start] = 0;
	pq.push(make_pair(-0, start));
	come_from[start] = -1; //start 이전 지점은 없으므로 -1을 저장한다

	//다익스트라 알고리즘을 이용하여 start에서 dest로 가는 최단 거리를 저장한다
	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (short_dest[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < short_dest[there])
			{
				short_dest[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
				come_from[there] = here; //there은 here지점에서 온것이라고 저장한다
			}
		}
	}

	//dest로 온 경로를 구한다
	pathFind(dest);

	return short_dest[dest];
}

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

	int u, v, c;
	int start, dest;

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> c;

		adj[u].push_back(make_pair(c, v)); //pair에 비용, 도착지 순서로 저장한다
	}

	cin >> start >> dest;

	cout << Solve(start, dest) << "\n";
	cout << path.size() << "\n";
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << " ";

	return 0;
}