최단 경로의 개수 구하기

어떤 최단 경로 문제든 최단 경로의 개수를 구하는 방법은 똑같습니다. 현재 방문한 꼭짓점 $u$가 꼭짓점 $v$와 가중치 $w$인 변으로 연결되어 있을 때 $d(v) > d(u) + w$이면 $d(v)$를 $d(u)+w$로 업데이트하고 $c(v)$에 $c(u)$를 대입합니다. 물론 동시에 적절히 큐나 우선순위 큐에도 넣어주면 되죠. $d(v) = d(u) + w$이면 $c(v)$에 $c(u)$를 더해주면 됩니다. 여기서 $d(v)$은 꼭짓점 $v$까지 가는 최단 거리이고 $c(v)$는 그 최단 거리의 개수입니다. 시작점 $s$에서는 당연히 $d(s)=0$, $c(s)=1$입니다.

응용

BOJ 11084:: 나이트의 염탐

icpc.me/11084

BFS로 최단 경로의 개수를 구하는 문제입니다. 가중치 $w$는 모두 1이라고 가정하고 최단 경로의 개수 배열 $c$를 업데이트 하면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using Pint = pair<int, int>;
using Tint = tuple<int, int, int>;

int r, c;
int dist[400][400];
int cnt_path[400][400];

constexpr int adj[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
constexpr int INF = 1000000000;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> r >> c;
    
    fill(&dist[0][0], &dist[0][0] + 160000, INF);
    dist[0][0] = 0;
    cnt_path[0][0] = 1;

    queue<Pint> q;
    q.push({0, 0});

    while (!q.empty()) {
        auto [cr, cc] = q.front();
        q.pop();

        for (int k = 0; k < 8; k++) {
            int nr = cr + adj[k][0], nc = cc + adj[k][1];
            if (nr < 0 || nr >= r || nc < 0 || nc >= c)
                continue;
            if (dist[nr][nc] > dist[cr][cc] + 1) {
                q.push({nr, nc});
                dist[nr][nc] = dist[cr][cc] + 1;
                cnt_path[nr][nc] = cnt_path[cr][cc];
            }
            else if (dist[nr][nc] == dist[cr][cc] + 1)
                cnt_path[nr][nc] = (cnt_path[nr][nc] + cnt_path[cr][cc]) % 1000000009;
        }
    }

    if (dist[r-1][c-1] == INF)
        cout << "None";
    else
        cout << dist[r-1][c-1] << ' ' << cnt_path[r-1][c-1];

    return 0;
}

BOJ 14554:: The Other Way

icpc.me/14554

다익스트라 알고리즘으로 최단 경로의 개수를 구하는 문제입니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using Pint = pair<int, int>;
using Tint = tuple<int, int, int>;

using Pll = pair<ll, ll>;

ll n, m, s, e, a, b, c;
vector<Pll> adj[100000];
ll dist[100000];
ll cnt_path[100000];

constexpr ll INF = 1000000000000000000LL;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m >> s >> e;
    s--;
    e--;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        adj[a-1].push_back({b-1, c});
        adj[b-1].push_back({a-1, c});
    }

    fill(dist, dist+100000, INF);
    dist[s] = 0;
    cnt_path[s] = 1;

    priority_queue<Pll, vector<Pll>, greater<Pll>> pq;
    pq.push({0LL, s});

    while (!pq.empty()) {
        auto [cur_dist, cur] = pq.top();
        pq.pop();

        if (cur_dist > dist[cur])
            continue;
    
        for (auto [nxt, d] : adj[cur]) {
            if (dist[nxt] > dist[cur] + d) {
                dist[nxt] = dist[cur] + d;
                cnt_path[nxt] = cnt_path[cur];
                pq.push({dist[nxt], nxt});
            }
            else if (dist[nxt] == dist[cur] + d)
                cnt_path[nxt] = (cnt_path[nxt] + cnt_path[cur]) % 1000000009;
        }
    }

    cout << cnt_path[e];

    return 0;
}