[C++] 백준 1753 - 최단경로

• 문제

• 풀이 과정

• 최종 코드

• 잡담

백준 1753 : 최단경로
난이도 : 골드 4

시간 : 측정 x

 

 

 

문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

풀이 과정

 

출발 정점에서 다른 모든 정점까지 가는데 걸리는 최단 경로에 대한 비용을 구하면 된다.

다시 말해, 최소비용을 구하면 되는 문제이다.

 

이 문제에서는 음의 가중치가 없기 때문에 다익스트라 알고리즘으로 해결할 수가 있다.

 

처음에는 2차원 배열로 구현해보려고 했으나 20000 x 20000 x 4 = 256mb 를 초과한다.

따라서 우선순위 큐를 사용해서 구현했다.

 

우선순위 큐를 사용하기 위해서는 가장 큰 값이 top값으로 저장한다.

하지만 우리는 최솟값을 top으로 만들어야 한다.

따라서 우선순위 큐에 넣기 전에 가중치에 " -1 " 를 곱하여 가중치의 최솟값이 top이 되도록 한다.

 

그 후에는 인근해 있는 정점을 탐색하여 현재 저장되어 있는 비용값보다 작으면 업데이트 시켜준다.

 

 

최종 코드

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <cstring>

#define MAX 20001
#define INF 999999999

using namespace::std;

vector<pair<int, int>> graph[MAX];
int d[MAX];

int V,E,K;

int main(){
    scanf("%d %d", &V, &E);
    scanf("%d", &K);
    
    for(int i=0; i<E; i++){
        int t1,t2,t3;
        scanf("%d %d %d", &t1, &t2, &t3);
        graph[t1].push_back({t2,t3});
    }
    
    for(int i=1; i<=V; i++){
        d[i] = INF;
    }
    
    priority_queue<pair<int, int>> pq;
    pq.push({0,K});
    d[K] = 0;
    
    while(!pq.empty()){
        int wei = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        for(int i=0; i<graph[cur].size(); i++){
            int n = graph[cur][i].first;
            int nwei = graph[cur][i].second;
            
            if(d[n] > wei + nwei){
                d[n] = wei + nwei;
                pq.push({-d[n], n});
            }
        }
    }
    
    for(int i=1; i<=V; i++){
        if(d[i] == INF)
            printf("INF\n");
        else
            printf("%d\n", d[i]);
    }
}

 

 

 

잡담

다익스트라 알고리즘은 자료구조 시간 때 잠깐 배웠었는데 실제 사용은 처음해봤다.

good.