[알고리즘 문제] 백준1916 - 최소비용

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

다익스트라 알고리즘을 사용하여 해결하였습니다. 핵심은 우선순위 큐에 넣을 때 음수화, 뺄때 음수화를 해주는 것인데 이는 같은 도시로 비용이 적은 순으로 정렬하기 위함입니다. 예를 들어 [1,2],[1,3]을 그냥 넣게 되면 [1,3]이 [1,2]보다 높은 우선순위를 가지는데 [1,-2],[1,-3]의 경우 [1,-2]이 [1,-3]보다 높은 우선순위를 가지고 -에 다시 -를 붙여주면 양수가 되므로 최소비용이 적은 순으로 값을 가질 수 있습니다.

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

using namespace std;

int number = 6;
int INF = 1000000000;

vector<pair<int, int>> a[100001]; // 간선의 정보
int d[1001];                      // 최소 비용

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

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

        if (d[current] < distance)
        {
            continue;
        }

        for (int i = 0; i < a[current].size(); i++)
        {
            int next = a[current][i].first;
            int nextDistance = distance + a[current][i].second;

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

int main()
{

    int N, M, S, E;
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        d[i] = INF;
    }

    for (int i = 0; i < M; i++)
    {
        int q, w, e;
        cin >> q >> w >> e;
        a[q].push_back({w, e});
    }
    cin >> S >> E;
    dijkstra(S);

    cout << d[E] << endl;
    return 0;
}