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

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

1753번: 최단경로

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int V, E;
int start;
int u,v,w;

int arr[200001];  //정점
vector<pii>edge[300001]; //간선+가중치

void dijkstra()
{
    arr[start]=0;  //첫 시작점 초기화
    priority_queue<pii, vector<pii>, greater<pii>>pq; //비용이 작은 것부터
    pq.push({0, start}); //비용, 시작점
    while(!pq.empty())
    {
        auto [cost, cur] = pq.top();
        pq.pop();

        if(arr[cur] < cost) continue;

        for(int i=0; i<edge[cur].size(); i++)
        {
            int next = edge[cur][i].first; //다음 정점
            int ncost = cost + edge[cur][i].second;  //다음 비용

            if(arr[next] > ncost) 
            {
                arr[next] = ncost;
                pq.push({ncost, next});
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> V >> E;  //정점, 간선
    cin >> start;   //시작점

    for(int i=1; i<=V; i++)
    {
        arr[i]=MAX;  //최댓값으로 초기화
    }

    for(int i=0; i<E; i++)
    {
        cin >> u >> v >> w;
        edge[u].push_back({v, w});  //방향그래프
    }

    dijkstra();

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

    return 0;
}

다익스트라 알고리즘 그자체인 문제이다.

저번에 달빛 여우라는 골드 1 짜리 다익스트라 문제를 풀면서 다익스트라에 대해 아직 잘 이해를 못한 것 같아서 조금 쉬운 걸로 풀게 되었다.

 

priority_queue<pii, vector<pii>, greater<pii>>pq

이 부분은 pq의 first가 작은 것부터 우선순위를 갖게 만드는 구문이다.

여기서 first를 비용으로 줬기 때문에 비용이 적게 드는 것부터 우선순위를 갖게 된다.

보통 비용을 우선순위로 만들기 때문에 저 구문을 사용하지 않는다면 비용에 -을 붙여서 음수로 처리한다.