[#1753] 최단 경로

/* 다익스트라 알고리즘
2차원 배열 이용시 시간복잡도 V의 제곱
우선순위 큐 이용시 시간복잡도 ElogV
*/
 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int main() {
    int v, e, k;
 
    scanf("%d %d", &v, &e);
    scanf("%d", &k);
 
    //max heap 인데 최소값을 pop해야 하므로 push할때 first 음수로 바꿔서 넣기
    priority_queue<pair<int, int>> pq; //first=최단거리, second=노드번호
    vector<int> distance(v + 1, INT_MAX);  //최단거리
    vector<vector<pair<int, int>>> adj(v + 1);  //인접리스트
 
    //vector<vector<int>> adj(v + 1, vector<int>(v + 1, INT_MAX));
 
    for (int i = 1; i <= e; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(make_pair(v, w));
    }
    distance[k] = 0;  //시작점의 최단거리는 0
    pq.push(make_pair(0, k));  //시작점 우선순위 큐에 넣어놓기
 
    while (!pq.empty()) {
        //dist 가장 작은 거 pop
        int here = pq.top().second;
        int hereDistance = -1 * pq.top().first;  //넣을때 음수해서 넣었으므로 -1 곱해주기
        pq.pop();
 
        //인접노드에 대해 dist 값 갱신
        for (int i = 0; i < adj[here].size(); i++) {
            int there = adj[here][i].first;
            int hereThereW = adj[here][i].second;  //here와 there 사이 거리
 
            if (distance[there] > distance[here] + hereThereW) {
                //visit 확인할 필요가 없는 이유는 갱신됐을때만 우선순위 큐에 넣어줘서
                //큐에 한번 들어갔던 노드는 갱신될리가 없으므로 넣어진적 있는지 없는지
                //확인할 필요 없음
                distance[there] = distance[here] + hereThereW;  //최단거리 갱신
                pq.push(make_pair(-distance[there], there));  //pq에 넣어주기. 음수로 바꿔서
            }
        }
 
    }
 
    for (int i = 1; i <= v; i++) {
        if (distance[i] == INT_MAX)
            printf("INF\n");
        else
            printf("%d\n", distance[i]);
    }
 
    return 0;
}

 

다익스트라 알고리즘

처음에는 2차원 배열로 구현했다가 시간초과 나와서 우선순위 큐 이용