문제 출처

1. 문제설명

  • N개의 도시가 있고 도시 간 이동 시 비용이 발생한다.
  • 시작점과 도착점이 주어졌을 때 최단 경로를 구하라
    • 비용, 최단 경로 개수, 최단 경로 출력
  • 문제 분류
    • Graph, Dijkstra


2. 알고리즘 설계

  • 평범한 다익스트라 문제라고 생각했지만, 엄청나게 맞왜틀을 시전했었다.
  • 그 이유는, 방문해보지 않아도 최단 경로가 아닌 지점에 대한 예외 처리였다.
    • 현재 비용이 최소 비용보다 작으면 방문할 필요가 없다.
    • if(cur.cost > dist[cur.node]) continue;
  • 이 예외만 잘 처리해주면, 일반적인 다익스트라 문제랑 똑같다!
  • 경로 순서 저장
    • 이건 어쩔 수 없이 추가 배열을 사용해야 한다.
    • 우선순위 큐에 넣을 때(값을 갱신할 때)마다 이전 위치를 업데이트 해준다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int INF = 987654321, SZ = 1002;
int n, m, src, dest;
vector<pii> adj[SZ];
int dist[SZ], route[SZ];

void dijkstra() {
    priority_queue<pii> pq;
    pq.push({ 0, src });
    dist[src] = 0;

    while (!pq.empty()) {
        pii cur = pq.top();
        pq.pop();

        if(cur.first > dist[cur.second]) continue;

        for(pii nxt : adj[cur.second]) {
            int next = nxt.first;
            int nc = cur.first + nxt.second;

            if(dist[next] > nc) {
                pq.push({nc, next});
                dist[next] = nc;
                route[next] = cur.second;
            }
        }
    }
}

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

    cin >> n >> m;
    for (int a, b, c; m--;) {
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
    }

    fill(dist, dist + n + 1, INF);

    cin >> src >> dest;

    dijkstra();
    cout << dist[dest] << '\n';

    vector<int> res;
    while(dest != 0) {
        res.push_back(dest);
        dest = route[dest];
    }

    cout << res.size() << '\n';
    for(auto it = res.rbegin(); it != res.rend(); it++)
        cout << (*it) << ' ';


    return 0;
}