11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시
www.acmicpc.net
- inf = |V| * max(weight) = 1억
- 경로 기록
- v의 기존 경로보다 u를 경유하는 것이 더 빠를 때
- v의 경로를 u 경유로 수정 & v의 부모를 u로 갱신
- 경로 출력
- dst vertext부터 부모를 따라가면서 src까지 벡터에 push_back
- src는 부모가 없으므로 부모 배열 값이 갱신되지 않고, 초기값(prnt[src] == 0) 그대로이다.
- 벡터를 역방향으로 순회하여 src ~ dst 순으로 경로 출력
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M, src, dst;
vector<pair<int, int>> adj[1001];
int inf = 100000000;
int dist[1001];
int prnt[1001];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M;
while (M--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
}
cin >> src >> dst;
fill(dist + 1, dist + N + 1, inf);
dist[src] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, src));
while (!pq.empty()) {
int w = -pq.top().first, u = pq.top().second;
pq.pop();
if (dist[u] < w) continue;
for (auto v : adj[u]) {
// 기존 v 경로보다 u를 경유하는 것이 최적
if (dist[u] + v.second >= dist[v.first]) continue;
// v의 경로를 u 경유하는 것으로 갱신
prnt[v.first] = u; // v의 부모를 u로 갱신
dist[v.first] = dist[u] + v.second;
pq.push(make_pair(-dist[v.first], v.first));
}
}
// 경로를 벡터에 담기
vector<int> route;
for (int u = dst; u; u = prnt[u]) { // dst vertex부터 부모가 없는 vertex(=src)까지
route.push_back(u);
}
// 벡터를 역순으로 출력하기
cout << dist[dst] << '\n' << route.size() << '\n';
for (auto rit = route.rbegin(); rit != route.rend(); ++rit) {
cout << *rit << ' ';
}
return 0;
}