반응형
문제링크: https://www.acmicpc.net/problem/11779
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스
www.acmicpc.net
다익스트라 문제이고, 추가 사항은 최소 경로를 구해야 하는 것이었습니다.
다익스트라는 일반적인 우선순위 큐 방식을 사용하였고, 경로를 저장하기 위해서는 자신의 출발지 값을 저장하게끔 구성을 해주었습니다.
접근방식
1. 일반적인 다익스트라 방식을 생각함
2. 최소 경로를 구하기 위해서 배열을 생성하고 출력
문제풀이
1. 일반적인 다익스트라 구현
2. 최소 경로를 구하기 위해서 배열을 생성함
해당배열에는 자신의 부모정점을 저장함.
ex) 1->3이면 arr[3] = 1
3. 해당 배열에서 while문을 사용하여 결과를 도출함
일부 예외처리를 신경써주어야 했음.
아래 처럼 탐색할 필요없는 정점이라면 가지치기를 해주어야 통과할 수 있는 문제.
if (cost > dist[cur])
continue;
가지치기를 해주어야 하는점이 꽤나 까다로운 문제였습니다.
정답코드입니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int cnt = 0;
int dist[1001];
int before_val[1001] = { 0, };
vector <pair<int, int>> vec[1001];
int n, m, s, e; // 도시 개수, 버스의 개수, 출발지, 도착지
void dijkstra() {
priority_queue <pair<int, int>> pq;
pq.push(make_pair(0, s));
dist[s] = 0;
while (!pq.empty()) {
int cost = - pq.top().first;
int cur = pq.top().second;
pq.pop();
if (cost > dist[cur])
continue;
for (int i = 0; i < vec[cur].size(); i++) {
int ncost = vec[cur][i].second;
int ncur = vec[cur][i].first;
if (dist[ncur] > cost + ncost) {
dist[ncur] = ncost + cost;
pq.push(make_pair(-dist[ncur], ncur));
before_val[ncur] = cur;
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
dist[i] = 2000000000;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
vec[a].push_back(make_pair(b, c));
}
cin >> s >> e;
dijkstra();
vector <int> arr;
arr.push_back(e);
int val = before_val[e];
while (val) {
arr.push_back(val);
val = before_val[val];
}
cout << dist[e] << endl;
cout << arr.size() << endl;
for (int i = arr.size() - 1; i >= 0; i--) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}반응형
'알고리즘 > 다익스트라' 카테고리의 다른 글
| [백준] 11404-플로이드(C++) (0) | 2021.07.30 |
|---|---|
| [백준] 9370-미확인 도착지(C++) (0) | 2021.07.26 |
| [백준] 4485-녹색 옷 입은 애가 젤다지?(C++) (0) | 2021.05.26 |
| [백준] 1504-특정한 최단 경로(C++) (2) | 2021.05.21 |
| [백준] 1916-최소비용 구하기 (0) | 2020.08.09 |