백준 14284번 간선 이어가기 2 C++ 다익스트라

리뷰

문제 정보가 좀 애매해서 정답 도출에 어려움을 겪었다, 그냥 다익스트라로 s 부터 t까지의 최단 경로를 구하면 된다.

 

문제 풀이

n, m값을 입력 받고 인접 리스트를 n + 1 크기로, 거리 벡터를 n + 1, 값을 최대한 크게 설정해 준다.

연결이란 두 정점이 간선을 통해 방문 가능하다고 문제에 쓰여있으니 양방향 이동이 가능하다.

시작 노드와 목적지 노드를 입력 받고 시작 노드를 힙에 추가, 시작노드의 거리를 0으로 초기화 한다.

while 루프를 시작해 시작 노드로 부터 각 노드까지의 최단 경로를 찾아 준다.

이후 목적지 까지의 노드를 출력해 주면 된다.

 

참고 사항

특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. << 이 조건은 실제 문제 풀이에 영향이 없다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정 << 이조건 또한 마찬가지

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 999999999;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> lst(n + 1);
    vector<int> dist(n + 1, INF);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        lst[a].push_back({ c, b });
        lst[b].push_back({ c, a });
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    int sn, dn;
    cin >> sn >> dn;

    pq.push({ 0, sn });
    dist[sn] = 0;

    while (!pq.empty()) {
        pair<int, int> cur = pq.top(); pq.pop();
        int cd = cur.first, cn = cur.second;
        if (dist[cn] != cd) continue;

        for (pair<int, int> next : lst[cn]) {
            int nd = next.first, nn = next.second;
            if (dist[nn] > cd + nd) {
                dist[nn] = cd + nd;
                //if (nn == dn) break;
                pq.push({ dist[nn], nn });
            }
        }
    }
    cout << dist[dn];
}