[백준 - 1916] 최소비용 구하기 - C++

분류: 다익스트라 /

 

문제

문제 링크

문제 설명

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

 

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_DIST = 1e9;

struct xd {int x, d;};
vector<xd> adj[1001];
int dist[1001];

bool cmp(const xd &a, const xd &b) { return a.d > b.d; }
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M; cin >> N >> M;
    while(M--) {
        int from, to, w; 
        cin >> from >> to >> w;
        adj[from].push_back({to, w});
    }
    int src, dest; cin >> src >> dest;
    for(int i=1; i<=N; i++) dist[i] = MAX_DIST;
    priority_queue<xd, vector<xd>, decltype(&cmp)> pq(cmp);
    
    dist[src] = 0;
    pq.push({src, 0});
    while(not pq.empty()) {
        const auto [x, d] = pq.top(); pq.pop();
        
        if(d > dist[x]) continue; // 중요❗️❗️❗️⭐️
        
        for(const auto &[nx, nw]:adj[x]) {
            if(dist[nx] <= dist[x] + nw) continue;
            dist[nx] = dist[x] + nw;
            pq.push({nx, dist[nx]});
        }
    }
    cout << dist[dest];
}

전형적인 다익스트라 문제

늘 그렇듯 다익스트라를 구현했으나 결과는 시간초과 [제출 코드] 

 

어디서 잘못된걸까? 

다익스트라를 처을 짤때 우선순위 큐에 중복으로 정점이 들어가는 것이 마음에 걸렸지만

어차피 거리 비교하는 부분(`if(dist[nx] <= dist[x] + nw) continue;`)에서 걸러지므로 신경쓰지 않았다.

지금까지 다익스트라 문제에서 위 코드도 잘 통과되었으니 크게 신경쓰지 않고 다익스트라 풀이를 정형화 시켰다.

그러다 이 문제에서 그동안 잘못 짰던 코드가 걸린 것이다. 너무 고마운 문제다.

 

시간초과 풀이의 경우 우선순위 큐(`pq`)에 정점이 중복해서 들어가게된다. 

큐에 한번 들어간 정점은 큐에서 나와 인접한 모든 정점에 대해 간선완화를 수행한다. 

나가는 간선이 많은 정점이 여러번 중복해서 `pq`에 들어갈 경우 시간초과 판정을 받을 수 있다.

[잘 설명되어있는 글]

 

따라서 큐에서 꺼낸 정점이 현재까지 최단거리인 정점에 대해서만 인접 정점에 대해 간선완화를 시켜야한다.

❗️`if(d > dist[x]) continue;`

참로 등호는 마지막으로 넣은 `x`의 거리가 현재까지 `x`의 최단거리일때 성립한다.

(`push({ nx, dist[nx] })  ->  dist[top().x] == top().d`)