[백준 C++] 1653번 최단경로

1753번: 최단경로

문제 요약

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

사용 알고리즘

다익스트라

입출력

• 입력: 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
• 출력: 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다. ``` 예제1

입력 5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6 출력 0 2 3 7 INF

## 풀이
다익스트라 알고리즘을 짜면 풀리는 문제이다. 정점과 가중치를 담는 큐를 만든다. 이 큐는 가중치를 기준으로 하는 우선순위 큐여야 한다. 그리고 맨처음에 이 큐에 정점은 k, 가중치는 0인 것을 담고 while문을 시작한다. 가중치가 가장 작은 것을 가져와 그것을 k와의 거리로 정하고 이 노드에서 이어지는 다른 경로의 값도 큐에 넣는다. 이때 큐에 추가하는 가중치는 `방금 큐에서 꺼내온 가중치+노드에서 이어지는 다른 경로의 가중치`로 한다. 이렇게 하면 k노드를 기준으로 가장 가까운 것 부터 거리가 정해지고 정해진 노드를 경유해서 가는 경우까지도 모두 찾게 된다.

## 어려웠던 점
처음에 큐에 가중치를 합한것으로 안하고 그냥 현재 노드에서 다른 경로의 가중치만을 넣어서 틀렸다.

## 배운 점 / 느낀 점
왜인지 다익스트라를 쉬운 알고리즘이라고 생각했는데 생각보다 어려웠다. 확실히 기억해둬야 겠다. 내림차순 우선순위 큐도 기억해둬야 겠다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int v, e, k;
vector<bool> visit;
vector<vector<pair<int,int>>> g;
vector<int> d;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
int infity = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> v >> e >> k;
    visit = vector<bool>(v+1);
    d = vector<int>(v+1, infity);
    g = vector<vector<pair<int,int>>>(v+1, vector<pair<int,int>>());
    q = priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>();
    for(int i = 0; i < e; i++){
        int u, vv, w;
        cin >> u >> vv >> w;
        auto it = find_if(g[u].begin(), g[u].end(), [vv](const pair<int,int>& p) {
            return p.second == vv;
        });
        if(it != g[u].end()){
            it->first = min(it->first, w);
        }
        else{
            g[u].push_back({w,vv});
        }
    }
    d[k] = 0;
    q.push({0, k});
    while(!q.empty()){
        int vv = q.top().second;
        int w = q.top().first;
        q.pop();
        if(visit[vv]){
            continue;
        }
        visit[vv] = true;
        for (int i = 0; i < g[vv].size(); i++) {
            if(visit[g[vv][i].second]) continue;
            d[g[vv][i].second] = min(d[g[vv][i].second], g[vv][i].first+d[vv]);
            q.push({d[g[vv][i].second], g[vv][i].second});
        }
    }
    for (int i = 1; i <= v; i++) {
        if(d[i] == infity){
            cout << "INF\n";
        }
        else{
            cout << d[i] << '\n';
        }
    }

    return 0;
}