백준 14284번 간선 이어가기 2[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 다익스트라입니다. 다익스트라란 가중치 그래프에서 임의의 정점을 출발점으로 지정해 다른 정점까지의 최단 거리를 빠른 시간 내에 구할 수 있는 알고리즘입니다. 로직 구현 자체에는 BFS와 큰 차이점은 없습니다. 

 문제를 해석해보시면 간선을 순서대로 하나씩 추가하다가 정점 s와 정점 t가 간선을 통해 방문할 수 있는 상태가 되면 간선 추가를 중지합니다. 그 후 추가했던 간선들의 가중치 합을 구하려고 합니다. 여기까지만 읽었다면 다익스트라를 적용할 수 있는지는 확신이 들지 않습니다. 하지만 다음 문장에 s와 t가 연결되는 시점에서 추가된 간선의 가중치 합이 최소가 되도록 추가할 간선의 순서를 조정한다고 합니다. 즉, 저희는 입력으로 주어지는 순서대로 간선을 추가할 필요가 없어지죠. 만약, 이 문장이 없이 문제가 주어졌다면 저는 Union-Find를 적용해서 풀이할 것 같습니다.

 

2. 문제 풀이

 간선들을 모두 인접리스트에 추가합니다. 그 이유는 간선을 추가할 때 어느 시점에서 s와 t가 연결되는지 알 수 없기 때문입니다. 따라서 간선을 모두 추가해 다익스트라를 수행함으로써 s와 t의 최단 경로에 해당하는 간선들을 추려낼 수 있습니다. 그다음 우선순위 큐를 하나 선언한 다음 정점 s를 출발점으로 다익스트라 알고리즘을 수행합니다. 그 후 d[t]를 출력하시면 됩니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x3f3f3f3f;

int n, m, s, t;
vpi adj[5005];
int d[5005];

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    while(m--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({w, v});
        adj[v].pb({w, u});
    }
    cin >> s >> t;
    
    memset(d, 0x3f, sizeof(d));
    priority_queue<pi, vpi, greater<pi>> pq;
    d[s] = 0;
    pq.push({d[s], s});
    while(sz(pq)) {
        auto [cd, cur] = pq.top(); pq.pop();

        if(cd != d[cur]) {
            continue;
        }

        for(auto &[nd, nxt] : adj[cur]) {
            if(d[nxt] > d[cur] + nd) {
                d[nxt] = d[cur] + nd;
                pq.push({d[nxt], nxt});
            }
        }
    }

    cout << d[t];
}

 

4. 제출 결과