백준 - 1753 최단경로

문제 링크입니다 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

우선순위 큐에 push할 때, pair로 넣는데 이때 거리를 앞으로 두어서 속도를 좀 더 높여보자

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;
int V, E, K;
vector<vector<pair<int, int>>> vertex;
vector<int> dist;

void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();

        if(dist[cur] < distance) continue;

        for(int i = 0; i < vertex[cur].size(); i++) {
            int next = vertex[cur][i].first;
            int nextDist = distance + vertex[cur][i].second;

            if(nextDist < dist[next]) {
                dist[next] = nextDist;
                pq.push({-nextDist, next});
            }
        }
    }

}


int main() {
    cin >> V >> E >> K;
    vertex.assign(V + 1, vector<pair<int, int>>());
    dist.assign(V + 1, INF);

    int u, v, w;
    for(int i = 0; i < E; i++) {
        cin >> u >> v >> w;
        vertex[u].push_back({v, w});
    }

    dijkstra(K);

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

    return 0;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~