최단경로 1753

문제

접근 방법

다익스트라 알고리즘을 의도한 문제이다. 적용해주면 된다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<vector<pair<int, int>>> vertex; // 번호, 가중치
    vector<int> dis;
    int V, E, start;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 가중치, 번호
    cin >> V >> E >> start;
    --start;
    for (int i = 0; i < V; ++i)
    {
        dis.push_back(INT_MAX);
        vertex.push_back(vector<pair<int, int>>());
    }
    for (int i = 0; i < E; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vertex[u - 1].push_back({v - 1, w});
    }
    dis[start] = 0;
    pq.push({0, start});
    while (!pq.empty())
    {
        pair<int, int> curNode = pq.top();
        pq.pop();
        if (dis[curNode.second] < curNode.first)
            continue;
        for (int i = 0; i < vertex[curNode.second].size(); ++i)
        {
            pair<int, int> nextNode = vertex[curNode.second][i];
            if (dis[nextNode.first] > curNode.first + nextNode.second)
            {
                dis[nextNode.first] = curNode.first + nextNode.second;
                pq.push({dis[nextNode.first], nextNode.first});
            }
        }
    }
    for (int i = 0; i < V; ++i)
    {
        if (dis[i] == INT_MAX)
            cout << "INF";
        else
            cout << dis[i];
        cout << '\n';
    }
    return 0;
}

풀이

시작점을 기준으로 노드를 하나씩 방문해가며 최소 거리를 기록해가는 알고리즘이다.
이 문제에서 조심해야 할 점은 메모리 초과인 것 같다.
배열을 사용하기보다는 벡터를 사용해서 해결하면 된다.

간혹 w가 10 이하의 자연수란 이유로 dis의 값을 10보다 약간 높은 값으로 채워 넣는 경우가 있는데 가중치가 10 이하인 것이지 노드까지의 거리가 10 이하는 아니기에 오답이 날 것이다.