[1916] 최소비용 구하기

전형적인 다익스트라 알고리즘이다.
양방향 그래브가 아닌, 한 방향 그래프!

계속 틀렸었는데 이유는 두가지가 있었다.

1. 출발 노드에서 도착 노드로 갈때 가는 방법이 여러가지 일때 최소 비용으로 입력값을 받아야함. 이는 인접 리스트일 때는 상관이 없지만, 내가 쓰는 인접 행렬에서는 입력 받을 때 값이 갱신 되므로 이를 고려하여, 최소 비용으로 넣어주어야 한다.
2. INF 설정.

https://www.acmicpc.net/board/view/52042
Inf를 987654321로 바꿔야 한다.
간선의 비용이 1000000 이라고 해도, 노드의 개수가 1000개 이므로 최대값을 고려하면 100000 * 999 를 한다면 대략 최소 1억은 되어야 한다.

#include <iostream>
#include <algorithm>
using namespace std;
int a[2002][2002];
#define INF 987654321
int main(void)
{
    int n, m;
    cin >> n >> m;
    int ddest, ssrc;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                a[i][j] = 0;
            else
                a[i][j] = INF;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int src, dest, cost;
        cin >> src >> dest >> cost;
        a[src][dest] = min(a[src][dest], cost);
    }
    cin >> ssrc >> ddest;
    int count = n - 2;
    int check[1001] = {
        0,
    };

    while (1)
    {
        int min = INF;
        int minidx = -1;
        for (int i = 1; i <= n; i++)
        {
            if (a[ssrc][i] == INF)
                continue;
            if (check[i] == 0 && min > a[ssrc][i])
            {
                minidx = i;
                min = a[ssrc][i];
            }
        }
        //  cout << minidx << "min" << '\n';
        if (minidx == -1)
            break;
        check[minidx] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (a[minidx][i] == INF)
                continue;
            if (a[ssrc][minidx] + a[minidx][i] < a[ssrc][i])
            {
                a[ssrc][i] = a[ssrc][minidx] + a[minidx][i];
            }
        }
    }
    cout << a[ssrc][ddest];
    /* for (int i = 1 ; i<= n ; i++) {
        cout<< a[ssrc][i]<<' ';
    }*/
}```