[골5] 1916 - 최소 비용 구하기

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

#define INF 1e9 + 10
#define MAX 1001

#define y first
#define x second

using namespace std;
using IntPair = pair<int, int>;

vector<IntPair> g[MAX];
priority_queue<IntPair> pq;
vector<int> dist(MAX, INF);
int src, dst;

void Dijkstra()
{
    pq.push({ 0,src });
    dist[src] = 0;

    while(!pq.empty())
    {
        int cost = -pq.top().y;
        int cur = pq.top().x;
        pq.pop();

        if (dist[cur] < cost)
            continue;

        for (int i = 0; i < g[cur].size(); i++)
        {
            auto val = g[cur][i];
            int nxt   = val.y;
            int nCost = val.x + cost;

            if (dist[nxt] > nCost)
            {
                dist[nxt] = nCost;
                pq.push({ -nCost, nxt });
            }
        }
    }
}

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

    int n, m = 0, a, b, c;
    cin >> n >> m;

    while (m--)
    {
        cin >> a >> b >> c;
        g[a].push_back({ b,c });
    }
    cin >> src >> dst;
    Dijkstra();
    cout << dist[dst];
}