알고리즘 문제풀이
[백준/BOJ] 백준 11779번 : 최소비용 구하기 2
GeniusJo
2020. 9. 23. 02:17
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스�
www.acmicpc.net
다익스트라 알고리즘을 이용하여 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;
}