백준 1753번 - 최단경로 (C++)

해결 방법

다익스트라 문제.
시작 간선부터 시작해서, 내가 갈 수 있는 모든 지점의 최단거리를 기록해두고
우선순위 큐를 사용하여 그중 가장 낮은 지점부터 다시 모든 지점의 최단거리 기록을 반복한다.

+번외로 처음 입력받을 때, 출발지 목적지가 같은 가중치만 다른 간선이 여러개가 입력될 수 있어 최적화를 위해 이건 가장 짧은 간선 하나만 받아올 수 있도록 했다.

아쉬웠던 점

우선순위 큐의 존재를 모르고 일반 큐로 최소값 찾고 하면서 했다가 시간초과 나서 우선순위 큐는 검색을 통해 알게 되었다.

번외로, 기본적으로 우선순위 큐의 정렬은 오름차순인데 이걸 내림차순으로 변경하기 위해 자료형을 지정해주는게 참 괴상하게 생긴듯.

코드

#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
 
vector<map<int, int>> graph;
vector<int> minWeight;
// 내림차순 우선순위 큐
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int v, e, k;
    cin>> v >> e >> k;
 
    graph.resize(v + 1);
    minWeight.resize(v + 1, 99999999);
    
    for(int i=0;i<e;i++)
    {
        int point, target, weight;
        cin >> point >> target >> weight;
 
        //동일 간선 최솟값 제외 무시
        if(graph[point].count(target) != 0)
        {
            if(graph[point][target] > weight)
                graph[point][target] = weight;
        }
        else
            graph[point].insert({target, weight});
    }
 
    minWeight[k] = 0;
    pq.push({0, k});
 
    while (!pq.empty())
    {
        int curWeight = pq.top().first;
        int point = pq.top().second;
        pq.pop();
 
        // 이미 더 짧은 경로가 있으면 무시
        if (minWeight[point] < curWeight)
            continue;
 
        // 인접 노드 확인
        for (auto it : graph[point])
        {
            int target = it.first;  // 다음 노드
            int weight = it.second; // 가중치
 
            int totalWeight = curWeight + weight;
            if (totalWeight < minWeight[target])
            {
                minWeight[target] = totalWeight;
                pq.push({totalWeight, target});
            }
        }
    }
    
    for(int i = 1; i <= v; i++)
    {
        if (minWeight[i] == 99999999)
            cout << "INF" << endl;
        else
            cout << minWeight[i] << endl;
    }
    
    return 0;
}