[14284번][C/C++] 간선 이어가기 2

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

14284번: 간선 이어가기 2

 

1번부터 N번까지 번호가 붙은 노드가 있고, 양의 가중치를 가진 무방향 간선을 하나씩 그래프에 붙일 때, s노드와 t노드가 최초로 연결되는 순간이 있다.

간선들을 붙이는 순서를 마음대로 조정할 때, 이 s노드와 t노드가 최초로 연결되는 순간에 s노드와 t노드를 잇는 간선들의 가중치의 합이 최소가 되는 순간의 가중치의 합을 구하는 문제이다.

 

이 문제는 복잡하게 보일 수 있지만 생각해 보면 문제의 포인트는 다음과 같다.

간선의 순서를 마음대로 조정할 수 있으므로 s와 t가 언제 이어지냐는 전혀 중요하지 않다는 것이다.

 

왜 그럴까? 직관적으로는 이해가 되더라도 정확히 그게 왜 가능한지 이해가 되지 않는 사람들을 위해 설명을 해보자면 아래와 같다.

모든 간선을 가지고 s점에서 t점까지의 최단 거리를 찾는다면 그때 최단 거리를 구성하는 간선들이 있을 것이다.

다른 잡다한 간선들은 사용하지 않고, 그래프를 구성할 때 이 최단거리를 구성하는 간선들을 가장 먼저 입력받았다고 생각하면

그게 바로 s와 t노드가 최초로 연결되는 순간 중 s와 t노드를 잇는 간선들의 가중치의 합이 최소가 되는 간선의 입력 순서이다.

 

따라서 해결법은 다음과 같다.

우선 모든 간선을 다 입력받아서 그냥 그래프를 구성한 뒤, s노드나 t노드에서 다익스트라 알고리즘을 한 번 수행한 후, s에서 t노드로의 최단 거리를 출력하면 정답이다.

 

문제를 해석하고나면 그때부터는 그저 기본적인 다익스트라 구현 문제였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

#define INF 987654321

using namespace std;

vector<vector<pair<int,int>>> graph(5001);
int dist[5001];
int n, m;
int s, t;

void dijkstra() {
    priority_queue<pair<int, int>> pq;
    pq.push({0, s});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int cCost = -pq.top().first;
        pq.pop();

        for(int i=0;i<graph[cur].size();i++) {
            int next = graph[cur][i].first;
            int nCost = graph[cur][i].second;

            if (dist[next] > cCost + nCost) {
                dist[next] = cCost + nCost;
                pq.push({-dist[next], next});
            }
        }
    }
}

void init() {
    for(int i=0;i<5001;i++) {
        dist[i] = INF;
    }
}

int main() {
    init();

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

    dijkstra();

    printf("%d", dist[t]);

    return 0;
}