1753번

1753번 - 최단 경로

이 문제는 가중치가 있고, 방향이 있는 그래프에서 한점에서 나머지 점까지 최단 거리를 구하므로 

다익스트라, 벨만코드, 플로이드 워셜 알고리즘이 있다.

일단 노드의 수가 최대 2만개, 간선의 수가 최대 30만개로 많다.

벨만코드의 시간 복잡도는 O(VE) 이므로 2만*30만= 60억으로 , 1억을 1초라 하면 60초나 걸린다.

또한 플로이드 워셜 알고리즘은 O(V^3) 이므로 더 많은 시간이 걸린다.

따라서 가장 빠른 다익스트라 알고리즘을 사용해야 한다.

다익스트라 알고리즘도 2가지 방식이 있다. 하나는 priority queue 를 사용하는 방법과, 그렇지 않은 방법.

일단 priority queue 를 사용하면 O(ElogV) = 30만 * 15 = 450만으로 충분히 사용할 수 있다.

하지만 priority queue를 사용하지 않으면 O(V^2 + E) 이므로 이미 4억을 넘어가므로 사용할 수 없다.

따라서 이 문제는 priority queue를 이용한 다익스트라를 이용해서 풀어야 한다.

queue에 넣을 때 항상, -로 바꿔서 넣어야 한다는 거 잊지말자!!!!!!!!!

<정답 코드>  

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
 
const int INF = 987654321;
int main()
{
    int n, e, start;
    
    scanf("%d %d %d", &n, &e,&start);
 
    vector<vector<pair<int, int>>> v(n+1);
    vector<int> dist(n+1);
 
    for (int i = 0; i < e; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({ b,c });
    }
 
    for (int i = 1; i <= n; i++)
    {
        dist[i] = INF;
    }
 
    priority_queue<pair<int, int>> q;
 
    dist[start] = 0;
    q.push({ start,dist[start] });
 
    while (!q.empty())
    {
        int now = q.top().first;
        int cost = -q.top().second;
        q.pop();
 
        if (cost > dist[now])
        {
            continue;
        }
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i].first;
            int w = v[now][i].second;
 
            if (dist[next] > cost + w)
            {
                dist[next] = cost + w;
                q.push({ next,-dist[next] });
            }
        }
 
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] >= INF)
        {
            printf("INF\n");
        }
        else
        {
            printf("%d\n", dist[i]);
        }
    }
 
    
 
    return 0;
}