백준 #1753 최단경로


BOJ #1753 - 최단경로

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

# 문제 분류

최단 경로 찾기

풀이 접근 방법


  1. 다익스트라 알고리즘을 사용하면 된다.
  2. 그러나 개미들을 구분짓지 않는다면? 개미가 부딪혀 돌아가는 것을 그저 통과하는 것으로 볼 수 있다.
  3. 따라서 막대의 중간에서 가장 가까이 있는 개미가 끝을 향해 달리는 최단시간이 최소 시간이고,
  4. 막대의 양 끝단에서 가장 가까이 있는 개미가 반대편 끝을 향해 달리는 시간이 최대 시간이다.

최단 경로를 찾는 데 사용되는 알고리즘은 대표적으로 Floyd-Warshall, Bellman-Ford, Dijkstra, SPFA 네 알고리즘이 있다.
각각 O(V3)O(V^3), O(VE)O(VE), O(ElogV)O(E\log V), Oavg(E)O_{avg}(E) ~ Owor(VE)O_{wor}(VE)의 시간 복잡도를 갖고 있다.
Oavg(E)O_{avg}(E)인 SPFA를 사용하면 되지 않을까? 했지만 이미 테스트 케이스가 수정되어 시간초과가 뜬다 ㅜ
주어진 input size는 1≤V≤20,000, 1≤E≤300,000와 같으므로, 1초 내에 해결하기 위해선 다익스트라가 필수적이다.
(주어지는 가중치가 양수이기 때문에 사용할 수 있음을 알아야 한다.)

더 자세한 내용은 구사과님 포스트에서 알 수 있다.
사실 밑 코드는 포스트에 있는 것과 달리 방문하지 않기만 하면 pq에 때려박는 방법은 아니긴 하다,,

그리고 해당 문제에 관련된 이슈로 지적된 것들을 모은
백준에 있는 포스트 또한 읽어볼만한 가치가 있는 것 같다.

소스 코드


#include <stdio.h>
#include <vector>
#include <queue>
#define mk make_pair
#define MAXN 300010
#define MAX 1000000000

using namespace std;

int D[MAXN+1];
bool chk[MAXN+1];

vector<pair<int, int>> edge[MAXN+1];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main(){
    int n, m, i, a, b, d, s;

    scanf("%d %d", &n, &m);
    scanf("%d", &s);
    for(i=0; i<m; i++){
        scanf("%d %d %d", &a, &b, &d);
        edge[a].push_back(mk(b,d));
    }

    for(i=0; i<MAXN+1; i++) D[i] = MAX;

    D[s] = 0;
    pq.push(mk(0, s));
    while(!pq.empty()){
        int v = pq.top().second;
        pq.pop();

        if(chk[v]) continue;
        chk[v] = true;

        for(i=0; i<edge[v].size(); i++){
            int u = edge[v][i].first;
            int d = edge[v][i].second;

            if(D[u] > D[v] + d){
                D[u] = D[v] + d;
                pq.push(mk(D[u], u));
            }
        }
    }

    for(int i=1; i<=n; i++) {
        if (D[i] == MAX) {
            printf("INF\n");
        continue;
    }
        printf("%d\n", D[i]);
    }

    return 0;
}