[Greedy] 다익스트라 최단 경로

// 5972
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 2000000000;

int N, M;
struct Node
{
    int Idx;
    int Weight;
};

vector< vector<Node> > Graph;

struct cmp
{
    bool operator() (Node x, Node y)
    {
        return x.Weight > y.Weight;
    }
};


vector<int> Dijkstra(int Start)
{
    vector<int> Distance(N + 1, INF);
    priority_queue<Node, vector<Node>, cmp> Heap;

    Distance[Start] = 0;
    Heap.push( {Start, 0} );

    while ( !Heap.empty() )
    {
        int Now = Heap.top().Idx;
        int Dist = Heap.top().Weight;
        Heap.pop();

        if( Dist > Distance[Now] ) continue;

        for( Node NowNode : Graph[Now] )
        {
            int Next = NowNode.Idx;
            int Cost = NowNode.Weight;

            if ( Distance[Next] > Dist + Cost )
            {
                Distance[Next] = Dist + Cost;
                Heap.push( { Next, Distance[Next] } );
            }
            
        }
    }
    
    return Distance;
}

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

    cin >> N >> M;
    
    Graph.resize(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int A, B, C;
        cin >> A >> B >> C;

        Graph[A].push_back( { B, C } );
        Graph[B].push_back( { A, C } );
    }
    
    vector<int> Result = Dijkstra(1);
    cout << Result[N];
}

한 정점에서 다른 모든 정점까지의 최단 경로 구하기