백준 1753. 최단 경로 (다익스트라)

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

1. 특징

다익스트라 알고리즘을 이용하는 전형적인 문제. - 우선순위큐로 구현 

bfs처럼 암기해야될 코드일 것 같다. 

 

2. 코드

#include <iostream>
#include <queue>
using namespace std;

int v, e, st;
int d[20005]; // 최단 거리 테이블
vector<pair<int, int>> adj[20005]; // 비용, 정점번호
const int INF = 1e9+10;
int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> v >> e >> st;
    fill(d, d+v+1, INF);

    while(e--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(w, v));
    }

    //거리가 작은수부터 출력
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    d[st] = 0;

    //우선순위 큐에 {0, 시작점} 추가
    pq.push(make_pair(d[st], st));
    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        if(d[cur.second]!=cur.first) continue;
        for(auto nxt: adj[cur.second])
        {
            if(d[nxt.second] <= d[cur.second] + nxt.first) continue;
            d[nxt.second] = d[cur.second] + nxt.first;
            pq.push(make_pair(d[nxt.second], nxt.second));
        }
    }

    for(int i = 1; i <= v; i++)
    {
        if(d[i] == INF) cout << "INF\n";
        else cout << d[i] << "\n";
    }
    
}