백준 14554 - The Other Way (C++)

문제

• 문제 링크

  
   BOJ 14554 - The Other Way 
  

• 문제 요약

$N$개의 정점으로 이루어진 그래프와 출발지, 목적지가 주어진다.
출발지에서 목적지까지 최단 경로로 가는 경우의 가짓수를 구해보자.

• 제한

TL : $2$ sec, ML : $256$ MB




$2 ≤ N ≤ 100,000$

$N - 1 ≤ M ≤ 300,000$

알고리즘 분류

• 그래프 이론(graphs)
• 다익스트라(dijkstra)
• 다이나믹 프로그래밍(dp)

풀이

$S$에서 $E$까지의 최단 경로는 다익스트라를 이용해 쉽게 구할 수 있다.
넓게 보면 $S$가 중간 정점 $X$를 거치고 $E$로 도달할 때,
$S$ 에서 $X$로 가는 경우의 수 $*$ $X$에서 $E$로 가는 경우의 수 가 답이 된다.
(단, 최단 거리로 이동할 때 기준)

다익스트라의 흐름상,
$S$를 시작으로 $E$에 도달하기 까지의 과정이 $DAG$$(Directed$ $Acyclic$ $Graph)$를 이룬다.
여기서 경로의 수를 구해야 하므로 추가적인 배열 하나를 정의하자.

$rev[i] :$ 정점 $S$부터 정점 $i$ 까지 최단 거리로 도달하게 하는 이전 정점들의 집합.

구체적으로 현재까지 이동 거리 $d$, 정점 $s$에서 보고 있는 간선이 가중치 $w$로 정점 $x$를 이을 때,

$dist[x] == d + w$ 라면 $s$는 $rev[x]$에 포함될 수 있는 정점이다.

$dist[x] > d + w$ 라면 그동안의 $rev[x]$를 모두 날리고, $rev[x]$에 정점 $s$를 새로이 포함 시킨다.

---

위의 과정을 모두 마쳤다면, 이제 다익 역추적 문제처럼 $E$부터 $rev[E]$를 이용해 거꾸로 계산해 나갈 수 있다.

$dp[i]$ : $S$에서 $i$ 까지 가는 최단 경로의 가짓수

로 정의할 때 기저 사례는 당연히 $dp[S] = 1$ 이 되겠다.

일반적으로는, $dp[i] =$ $Σdp[rev[i][j]]$ $(1 ≤ j ≤ rev[i].size())$ $mod$ $1,000,000,009$
로 간단하게 계산해낼 수 있다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 100001
using namespace std;
 
vector <pair<int, int>> Gr[N];
vector <int> rev[N], dp(N);
vector <ll> dist(N, 1e18);
int n, m, s, e;
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> e;
    for (int i, j, w; m--;)
        cin >> i >> j >> w, Gr[i].emplace_back(j, w), Gr[j].emplace_back(i, w);
}
void Dijkstra()
{
    priority_queue<pair<ll, int>> Q;
    dist[s] = 0, dp[s] = 1;
    for (Q.push({ 0, s }); Q.size();)
    {
        auto [d, s](Q.top()); Q.pop();
        if (dist[s] >= -d)
            for (auto [x, w] : Gr[s])
                if (ll k = w - d; k <= dist[x])
                {
                    if (k ^ dist[x]) Q.push({ -k, x }), rev[x].clear();
                    dist[x] = k, rev[x].push_back(s);
                }
    }
}
int Solve(int p = e)
{
    if (!dp[p])
        for (int& i : rev[p])
            dp[p] = (dp[p] + Solve(i)) % 1000000009;
    return dp[p];
}
int main()
{
    Init();
    Dijkstra();
    cout << Solve();
}

comment

끝