알고리즘/BOJ
[C++] 백준 1753번 - 최단 경로
Jay, Lee
2022. 5. 13. 16:13
처음으로 다익스트라 문제를 풀어보았다.
학교에서 이제 막 다익스트라의 수도코드를 공부했는데, 실제로 구현해보니 너무 어려웠다.
특이하게 다익스트라는 1:1의 경로를 알기 위해서 1:N의 경로를 전부 구해야 문제를 해결할 수 있다는 점이었다.
어째뜬 문제에서 요구하는 것이 1:N의 경로를 요구하는 것이었기때문에 크게 문제가 되지는 않았다.
동아리에서 다익스트라에서 배울때는 변수 이름들을 u, v 등 vertex를 만들때 기본적으로 활용되는 이름들을 썼었는데,
이렇게 코드를 작성하다보니까 직관적으로 다가오지 않아서 변수 이름들을 좀 명확하게 써놓았다.
다익스트라에 좀 익숙해지면 변수명도 교체해야하지 않을까 싶다.
#include <bits/stdc++.h>
#define endl '\n'
#define INF 987654321
#define pii pair<int, int>
using namespace std;
int V, E, start;
vector<pii> graph[20010];
int dist[20010] = { 0, };
priority_queue<pii, vector<pii>, greater<pii>> pq;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> V >> E;
cin >> start;
for (int i = 0; i < E; i++) {
int u, v, w; cin >> u >> v >> w;
graph[u].push_back({ w, v });
}
for (int i = 1; i < V + 1; i++)
dist[i] = INF;
dist[start] = 0;
pq.push({ dist[start], start });
while (!pq.empty()) {
int distance = pq.top().first;
int current_vertex = pq.top().second;
pq.pop();
if (dist[current_vertex] < distance) continue;
for (int i = 0; i < graph[current_vertex].size(); i++) {
int next_vertex = graph[current_vertex][i].second;
int next_weight = graph[current_vertex][i].first;
if (distance + next_weight < dist[next_vertex]) {
dist[next_vertex] = distance + next_weight;
pq.push({ dist[next_vertex], next_vertex });
}
}
}
for (int i = 1; i < V + 1; i++) {
if (dist[i] == INF) cout << "INF" << endl;
else cout << dist[i] << endl;
}
return 0;
}