BOJ 1753번 최단경로

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

github : https://github.com/junho0956/Algorithm/blob/master/1753/1753/%EC%86%8C%EC%8A%A4.cpp

 

한 정점에서 다른 모든 정점으로의 최단거리를 구하려면

다익스트라의 개념을 활용해야 합니다.

일반적으로 구현하면N^2의 복잡도가 필요하기 때문에 우선순위 큐를 사용하여 NlogN 에 구현하였습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321
typedef pair<int, int> pii;
 
int vertex, edge;
vector<pii> v[20001];
priority_queue<pii, vector<pii>, greater<pii> > q;
int dist[20001];
bool visit[20001];
 
void dijkstra(int start) {
    for (int i = 1; i <= vertex; i++) dist[i] = INF;
    dist[start] = 0;
    q.push({ 0,start });
 
    while (!q.empty()) {
        int w = q.top().first;
        int node = q.top().second;
        q.pop();
 
        if (visit[node]) continue;
        visit[node] = true;
 
        for (int i = 0; i < v[node].size(); i++) {
            int cur = v[node][i].first;
            int weight = v[node][i].second;
            if (!visit[cur] && dist[cur] > w + weight) {
                dist[cur] = w + weight;
                q.push({ w + weight, cur });
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    int start_vertex;
    cin >> vertex >> edge >> start_vertex;
    for (int i = 0; i < edge; i++) {
        int s, e, w;
        cin >> s >> e >> w;
        v[s].push_back({ e,w });
    }
 
    dijkstra(start_vertex);
 
    for (int i = 1; i <= vertex; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
 
    return 0;
}