Baekjoon 1753번 최단경로

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int V, E;
    cin >> V >> E;
    vector<vector<pair<int, int>>> adj(V);
    int K;
    cin >> K;
    int u, v, w;
    for(int i = 0; i < E; i++){
        cin >> u >> v >> w;
        adj[u-1].push_back(make_pair(v-1, w));
    }
    // dijkstra
    vector<int> dist(V, INF);
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, K-1));
    dist[K-1] = 0;
    while(!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        for(int i = 0; i < adj[here].size(); i++){
            int there = adj[here][i].first;
            int nextDist = cost + adj[here][i].second;
            if(nextDist < dist[there]){
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    for(int i = 0; i < V; i++){
        if(dist[i] == INF) cout << "INF" << "\n";
        else cout << dist[i] << "\n";
    }
    return 0;
}

다익스트라 알고리즘의 목적과 복잡도만 기억하고 구현이 필요할 때 마다 이전에 풀었던 문제의 코드를 그대로 가져와 사용하던 버릇이 여기서 문제가 되었다.

언제부터인가 우선순위 큐에 들어가는 쌍의 순서가 {거리, 목적지} 가 아닌, {목적지, 거리} 로 구현을 해 왔고 |E|log|V| 복잡도를 만족시키지 못해 시간초과가 발생했었다.