그냥 단순한 다익스트라 알고리즘을 사용한 문제였다.
최근 본 코테에서 다익스트라가 나왔는데도 불구하고 생각이 안나 못풀었던 걸 생각하면ㅠㅠ 미리 왜 공부를 안했나 후회가 되는 문제였다.
참고 블로그: alswnsdl.tistory.com/13
이 블로그를 통해 우선순위를 이용한 다익스트라 알고리즘을 공부하였고 문제에 적용할 수 있었다.
#define _CRT_SECURE_NO_WARNINGS
#define INF 1e9
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int V, E, start, end;
int a, b, c;
cin >> V >> E;
vector<pair<int, int>> arr[1001];
int dist[1001];
for (int i = 0; i < E; i++) {
cin >> a >> b >> c;
arr[a].push_back({ b,c });
}
cin >> start >> end;
fill(dist, dist + V + 1, INF);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({ 0, start});
dist[start] = 0;
while (!pq.empty()) {
int cost = pq.top().first;
int here = pq.top().second;
pq.pop();
for (int i = 0; i < arr[here].size(); i++) {
int next = arr[here][i].first;
int ncost = arr[here][i].second;
if (dist[next] > dist[here] + ncost) {
dist[next] = dist[here] + ncost;
pq.push({ dist[next], next });
}
}
}
cout << dist[end];
return 0;
}
'알고리즘 공부 > C++' 카테고리의 다른 글
[C++] 백준 1707번: 이분 그래프 (0) | 2020.11.24 |
---|---|
[C++] 백준 1759번: 암호 만들기 (0) | 2020.11.10 |
[C++] 백준 1107번: 리모컨 (0) | 2020.11.05 |
[C++] 백준 2470번: 두 용액 (0) | 2020.11.04 |
[C++] 백준 1477번: 휴게소 세우기 (0) | 2020.11.03 |