[BOJ/C++] 1916 최소비용 구하기

출발 도시에서 도착 도시까지 최소 비용을 구하는 문제로 다익스트라 알고리즘을 이용해 문제를 해결할 수 있습니다

시간초과가 발생하여 시간 복잡도를 줄일 필요가 있습니다.

if(nowDist > dist[nowNode])
	coninue;

• 이미 방문한 노드 중 가중치가 현재 노드까지의 최단거리보다 크다면 최단거리를 업데이트 할 필요가 없습니다

// boj g5 1916
// 최소비용 구하기

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;

using Node = pair<int, int>;
static vector<vector<pair<int, int>>> G;
static vector<int> dist;

void dijkstra(int node);

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

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

    G.resize(N + 1);
    dist.resize(N + 1, INT_MAX);

    for(int i =1; i<=M; i++)
    {
        int v, e, w;
        cin >> v >> e >> w;

        G[v].emplace_back(e, w);
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start);

    cout << dist[end];
   

    return 0;
}


void dijkstra(int node)
{
    priority_queue<Node, vector<Node>, greater<>> pq;
    pq.push(make_pair(0, node));

    dist[node] = 0;

    while(!pq.empty())
    {
        Node now = pq.top();
        pq.pop();

        int nowNode = now.second;
        int nowDist = now.first;

        if (nowDist > dist[nowNode])
            continue;

        for(Node next : G[nowNode])
        {
            int nextNode = next.first;
            int weight = next.second;

            if(dist[nextNode] > dist[nowNode] + weight)
            {
                dist[nextNode] = dist[nowNode] + weight;
                pq.push(make_pair(dist[nextNode], nextNode));
            }
        }

        
    }

}