백준 1719번 택배 C++ 다익스트라

리뷰

다익스트라를 활용하되 최단 경로까지의 시간이 아닌, 최단 경로 중 가장 먼저 밟아야 하는 노드를 출력하는 문제

 

문제 풀이

1. 인접리스트를 n + 1크기로 초기화 해주고 가중치와 시작, 도착 노드를 양방향으로 추가해 준다.
2. 이제 각 노드에 대해 해당 노드를 시작점으로 하는 다익스트라를 돌려주면 된다.
3. 거리를 나타낼 dist 벡터를 n + 1 크기, 기본값을 10억으로 초기화 해주었다.
4. 경로를 나타낼 path 벡터를 n + 1 크기로 초기화 해주었다.
5. 최소 힙을 정의해 주고 거리를 0으로 시작 노드를 추가해 준뒤 시작 노드의 거리를 0으로 초기화 해준다.
6. 이후 일반적인 다익스트라 로직을 실행 하되, 경로가 갱신되었을 경우 path 벡터를 변경해 준다.
7. 만약 현재 노드의 path가 비어있을 경우 다음 노드의 경로에 다음 노드 자기 자신을 추가해 준다.
8. 만약 현재 노드의 path가 존재할 경우 다음 노드의 경로를 현재 노드로 교체하고 다음 노드를 push 해준다.
9. 이후 while 루프가 종료되면 각 노드를 순회하며 자기 자신에 대한 경로는 -로 출력, 아닌 경우 path 벡터의 가장 앞 요소를 출력해 주면 된다.

 

참고 사항

가장 앞의 노드를 출력하는 것이기 때문에 사실상 2차 벡터로 나타낼 필요는 없다, 1차 벡터로 초기화 해준 뒤 노드를 push해 주는 것이 아닌 현재 노드의 path로 값을 바꿔주기만 해도 된다.

 

 

정답 코드

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

using namespace std;

int n, m;
vector<vector<pair<int, int>>> lst;

void init() {
    lst.resize(n + 1);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        lst[a].push_back({ c, b });
        lst[b].push_back({ c, a });
    }
}

void bfs(int start) {
    vector<int> dist(n + 1, 999999999);
    vector<vector<int>> path(n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({ 0, start });
    dist[start] = 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 (path[cn].empty()) path[nn].push_back(nn);
                else path[nn] = path[cn];
                pq.push({ dist[nn], nn });
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i == start) cout << "-" << " ";
        else cout << path[i][0] << " ";
    }
    cout << "\n";
}

void solution() {
    for (int i = 1; i <= n; i++) {
        bfs(i);
    }
}

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

    cin >> n >> m;
    init();
    solution();
}