백준 1916 최소비용구하기(다익스트라) - C++

문제 설명

내 풀이

이번 문제는 다익스트라를 이용하면 쉽게 풀 수 있는 문제였다.
다익스트라 문제를 풀기전 먼저 문제조건을 하나를 확인해야하는데, 간선이 양방향인지 일방적인지 확인해야하는데, 문제에서 양방향 통행이 가능하다는 말이 없으므로, 간선의 방향이 일방적인것으로 간주하고 문제를 풀었다.

제 문제 로직으로는

1. 최단 거리 테이블 INF로초기화 한다.
2. 시작 노드 설정한다.
3. 우선순위 큐를 통해 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐서 다른 노드로 가능 비용을 계산하여 최단 거리 테이블을 갱신한다.
   더이상 방문 가능한 노드가 없을 때 까지 3, 4 과정을 반복했다.

코드

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

using namespace std;

int n,m;
vector<pair<int,int> > v[1001];
int dist[1001];

void djikstra(int start)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
    pq.push(make_pair(0,start));
    dist[start] = 0;
    while(!pq.empty())
    {
        pair<int,int> par = pq.top();   
        int now = pq.top().second;
        int nowcost = pq.top().first;
        pq.pop();
        if (dist[par.second] < par.first)     // 이미 거리비용이 , 큐에 담겨잇는 비용보다 작으면 skip
            continue;
        for (int i = 0; i < v[par.second].size(); i++)
        {
            int nextcost = v[par.second][i].second + nowcost;       // 다음 비용 = 지금 비용 + 다음 노드의 비용
            int next = v[par.second][i].first;                       // 다음 노드
            if (dist[next] > nextcost)                      // 만약에 다음 노드의 비용이 계산된 비용보다 클때 최신화
            {
                dist[next] = nextcost;
                pq.push(make_pair(dist[next],next));
            }
        }
    }

}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back(make_pair(b,c));
    }
    for (int i = 0; i <= n; i++)
    {
        dist[i] = 987654321;
    }
    int a, b;
    cin >> a >> b;
    djikstra(a);
    cout << dist[b];
    return 0;
}