[백준] 1753번 최단경로 (C++)

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다.
이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. (1 ≤ u, v ≤ V, 1 ≤ w ≤ 10)

예제 입력 1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.
시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 출력 1

0
2
3
7
INF

풀이

문제 해결 방법

이 문제는 다익스트라 알고리즘을 사용하여 해결할 수 있는 전형적인 최단 경로 문제입니다. 다음은 문제를 해결하는 단계입니다:

1. 그래프 표현: 인접 리스트를 사용하여 방향 그래프를 표현합니다.

2. 우선순위 큐 활용: 다익스트라 알고리즘을 효율적으로 구현하기 위해 우선순위 큐를 사용합니다.

3. 최단 거리 갱신: 시작점에서부터 각 정점까지의 최단 거리를 계속해서 갱신합니다.

4. 방문 체크: 이미 처리한 정점은 다시 처리하지 않도록 방문 체크를 수행합니다.

이 알고리즘의 시간 복잡도는 O(E log V)입니다. 여기서 E는 간선의 수, V는 정점의 수입니다.

코드

#include<queue>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<functional>

using namespace std;

typedef pair<int, int> pii;

int n, m, k;
vector<pii> mp[20001];
int dist[20001];
int visit[20001];
priority_queue<pii, vector<pii>, greater<pii> > pq;

int main()
{
    int i;
    scanf("%d%d%d", &n, &m, &k);

    int a, b, c;
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        mp[a].push_back({ b,c });
    }

    for (i = 1; i <= n; i++)
    {
        dist[i] = 1e9;
    }
    dist[k] = 0;
    pq.push({ 0,k });

    while (!pq.empty())
    {
        pii p = pq.top(); pq.pop();

        int x = p.second;
        if (visit[x] == 1) continue;

        visit[x] = 1;

        for (pii edge : mp[x])
        {
            int node = edge.first;
            int cost = edge.second;
            if (dist[node] > dist[x] + cost)
            {
                dist[node] = dist[x] + cost;
                pq.push({ dist[node], node});
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        if (dist[i] == 1e9)
            printf("INF\n");
        else
            printf("%d\n", dist[i]);
    }

    return 0;
}