https://www.acmicpc.net/problem/1753
문제 해설가장 기본적이고 정형화된 다익스트라 문제이다!
다익스트라 알고리즘에서는 우선순위 큐를 사용하는데 기본적으로 우선순위 큐는 값이 큰 것부터 우선적으로 나가게 된다.
#include <bits/stdc++.h>using namespace std;#define INF 987654321int V, E;int startPoint;int dist[20002]; // dist[x] : 시작점으로부터 점 x까지의 최단 거리를 저장한다.vector<vector<pair<int, int>>> graph;void dijkstra(int start) { // 초기값은 무한대로 설정해 놓는다. for (int i = 1; i < V + 1; i++) { dist[i] = INF; } priority_queue<pair<int, int>> pq; pq.push({0, start}); dist[start] = 0; while (!pq.empty()) { int cntDist = -pq.top().first; int cntVertex = pq.top().second; pq.pop(); // 현재 점까지의 거리와 저장된 최단거리를 비교한다. // 현재 점까지의 거리가 더 큰 경우는 나중에 최단거리가 갱신된 것이다. // 우리는 각 점에 최단거리로 간 상태에 대해서만 갱신을 진행하므로 밑의 연산은 진행하지 않는다. if (cntDist > dist[cntVertex]) { continue; } // 아래 로직을 대신 사용해도 결과는 똑같이 나온다. // 즉 현재 점까지의 거리가 최단거리까지와 일치하는지 확인하는 단계이다. // if (cntDist != dist[cntVertex]) { // continue; // } for (int i = 0; i < graph[cntVertex].size(); i++) { int nextVertex = graph[cntVertex][i].first; int weight = graph[cntVertex][i].second; // cntDist 대신 dist[cntVertex]를 사용해도 결과는 동일하다 // int nextDist = dist[cntVertex] + weight; int nextDist = cntDist + weight; if (dist[nextVertex] > nextDist) { dist[nextVertex] = nextDist; // 값을 음수로 저장해 우선순위가 반대가 되도록 한다. pq.push({-nextDist, nextVertex}); } } }}int main(void) { cin >> V >> E; cin >> startPoint; graph = vector<vector<pair<int, int>>>(V + 1); for (int i = 0; i < E; i++) { int a, b, weight; cin >> a >> b >> weight; graph[a].push_back({b, weight}); } dijkstra(startPoint); for (int i = 1; i <= V; i++) { if (dist[i] == INF) { cout << "INF" << '\n'; } else { cout << dist[i] << '\n'; } } return 0;}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 우선순위 큐에 greater<pair<int, int>>> pq 정렬 방식을 통해 값이 작은 것부터 우선적으로 나가게 된다.
#include <iostream>#include <vector>#include <queue>using namespace std;#define INF 2000000000// 정점의 개수 : v, 간선의 개수 : eint v, e;vector<vector<pair<int, int>>> graph;vector<int> dist;vector<bool> check;int start_node;void dijkstra(){ for (int i = 1; i <= v; i++) dist[i] = INF; dist[start_node] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start_node}); while (!pq.empty()) { int weight = pq.top().first; int cnt_node = pq.top().second; pq.pop(); if (check[cnt_node] == true) continue; check[cnt_node] = true; // 점 cnt_node에 연결된 간선의 개수 int edge_num = graph[cnt_node].size(); for (int j = 0; j < edge_num; j++) { // from : 현재 위치, to : 다음 위치, from_to_weight : 현재위치에서 다음위치 까지의 가중치 int from = cnt_node, to = graph[cnt_node][j].first, from_to_weight = graph[cnt_node][j].second; if (dist[to] > dist[from] + from_to_weight) { dist[to] = dist[from] + from_to_weight; pq.push({dist[to], to}); } } }}int main(void){ scanf("%d %d %d", &v, &e, &start_node); dist = vector<int>(v + 1, INF); check = vector<bool>(v + 1, false); graph = vector<vector<pair<int, int>>>(v + 1); for (int i = 0; i < e; i++) { int from, to, weight; scanf("%d %d %d", &from, &to, &weight); graph[from].push_back({to, weight}); } dijkstra(); for (int i = 1; i <= v; i++) { if (dist[i] == INF) printf("INF\n"); else { printf("%d\n", dist[i]); } } return 0;}