Baekjoon 1916.최소 비용 구하기 c++ [Gold V]

https://graphonline.top/en/

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> graph(N + 1);
    for (int i = 0; i < M; i++)
    {
        int s, e, c;
        cin >> s >> e >> c;
        graph[s].push_back({e, c});
    }

    int startCity, endCity;
    cin >> startCity >> endCity;

    vector<int> dist(N + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, startCity});
    dist[startCity] = 0;

    while (!pq.empty())
    {
        int cost = pq.top().first;
        int current_city = pq.top().second;
        pq.pop();

        if (dist[current_city] < cost)
            continue;

        for (auto &neighbor : graph[current_city])
        {
            int next_city = neighbor.first;
            int next_cost = cost + neighbor.second;

            if (next_cost < dist[next_city])
            {
                pq.push({next_cost, next_city});
                dist[next_city] = next_cost;
            }
        }
    }

    cout << dist[endCity] << endl;

    return 0;
}

입력

5

8

1 2 2

1 3 3

1 4 1

1 5 10

2 4 2

3 4 1

3 5 1

4 5 3

1 5

개념

https://velog.io/@hunbot/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 설명

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> graph(N + 1);
    for (int i = 0; i < M; i++)
    {
        int s, e, c;
        cin >> s >> e >> c;
        graph[s].push_back({e, c});
    }

graph = {
    {},                     // 0번 인덱스 (사용하지 않음)
    {{2, 2}, {3, 3}, {4, 1}, {5, 10}}, // 1번 노드와 연결된 도시와 비용
    {{4, 2}},              // 2번 노드와 연결된 도시와 비용
    {{4, 1}, {5, 1}},      // 3번 노드와 연결된 도시와 비용
    {{5, 3}},              // 4번 노드와 연결된 도시와 비용
    {}                     // 5번 노드와 연결된 도시 (없음)
};

    vector<int> dist(N + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, startCity});
    dist[startCity] = 0;

dist 배열은 각 노드의 최단 거리를 저장하는 배열
N+1 => 노드가 1번부터 시작하기에
INT_MAX => 방문하지 않은 노드는 무한대의 값

dist[Inf,0,Inf,Inf,Inf..] 이런 식으로 되어 있음

priority_queue(우선 순위 큐) -> 개념 부분에 설명

    while (!pq.empty())
    {
        int cost = pq.top().first;
        int current_city = pq.top().second;
        pq.pop();

        if (dist[current_city] < cost)
            continue;

        for (auto &neighbor : graph[current_city])
        {
            int next_city = neighbor.first;
            int next_cost = cost + neighbor.second;

            if (next_cost < dist[next_city])
            {
                pq.push({next_cost, next_city});
                dist[next_city] = next_cost;
            }
        }
    }

    cout << dist[endCity] << endl;

첫 루프

cost : 0 / current_city : 1 / pq내부에 { {0,1} } pop => pq { }

넘어가서

next_city = 2 / next_cost = 0 + 2;

if( 2 < Inf ) 조건 성립 -> pq {(1, 4), (2, 2), (3, 3), (10, 5)}

dist[Inf,0,2,3,1,10]

두 번째 루프

cost = 1 / current_city = 4

pq = { {2, 2}, {3, 3}, {10, 5} };

if( 1 < 1) 조건 X

for문

next_city=5

next_cost=1+3=4

if( 4 < 10 )

pq = { {2, 2}, {3, 3}, {4, 5}, {10, 5} };