[백준 1916] 최소비용 구하기

최소비용 구하기

문제설명

각 도시들의 정보를 입력받고, 출발도시에서 도착도시까지 가는데 드는 최소 비용을 구하자.

알고리즘

1. 값을 각각 입력 받는다. pair형태의 백터 배열에 시작점, 도착점 ,cost를 입력받는다.
2. dist 배열을 INF로 초기화 시켜준다.
3. priority_queue를 사용하여 현재 비용, 시작 도시를 넣어준다.
4. 우선순위 큐에서 비용을 끄내는데 부호를 음수로 설정하고, 현재 도시를 꺼낸뒤 큐에서 지운다.
5. 현재 거리비용이 만약 지금 꺼낸 거리의 비용보다 작으면 넘어간다.
6. 반복문으로 이웃한 부분의 비용과 값을 확인한다.
7. 확인한 값이 최소경로인 경우 거리를 갱신해주고 다시 큐에 넣는다.

---

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 1001
#define INF 987654321
using namespace std;
int N, M;
int graph[MAX][MAX];

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    vector<pair<int ,int>> bus[100001];

    for (int i = 0; i < M; i++)//정보 입력 받기
    {
        int a, b, c;
        cin >> a >> b >> c;
        bus[a].push_back({ b,c });
    }
    int start, end;
    cin >> start >> end;//시작점과 도착점 입력

    int dist[MAX];
    fill(dist, dist + MAX, INF);

    priority_queue<pair<int, int>>pq;

    dist[start] = 0;//자기자신의 비용 =0
    pq.push({ 0,start });//초기비용, 시작점 넣기

    while (!pq.empty())
    {
        int cst = -pq.top().first;//거리가 작은 버스 부터 
        int current = pq.top().second;

        pq.pop();

        //최소 거리를 위한 
        if (dist[current] < cst) continue;

        for (int i = 0; i < bus[current].size(); i++)//이웃 확인
        {
            int next = bus[current][i].first;
            int nextcost = cst+bus[current][i].second;

            if (dist[next] >  nextcost)//최소 경로 발견
            {
                dist[next] =  nextcost;//갱신
                pq.push({ -nextcost,next });//거리가 작은 버스부터 꺼낼 수 있도록
            }
        }
    }

    cout << dist[end];
    return 0;
}

고찰

다익스트라 알고리즘을 우선순위큐를 활용하여 시간복잡도를 줄인 문제였다.
처음 해보는 유형이라서 이해하기 다소 힘들었다.
풀면서 INF값을 충분히 크게하지 않아서 중간에 42%에서 계속 오답이 났었다. 수의 범위도 중요한데 체크하지 않은 실수였다.