14554번: The Other Way

https://www.acmicpc.net/source/5852286


$O(m\lg n)$

최단경로를 따라 DAG를 만들고 DP를 한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, s, e, dp[MXN + 1];
long long dis[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
priority_queue<pair<long long, int> > pq;
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &e);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    fill(dis + 1, dis + 1 + n, 1e18);
    dis[s] = 0;
    dp[s] = 1;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int tpos = pq.top().second;
        long long tdis = -pq.top().first;
        pq.pop();
        if (dis[tpos] ^ tdis) continue;
        for (auto it : adj[tpos]) {
            if (it.second + tdis < dis[it.first]) {
                dis[it.first] = it.second + tdis;
                dp[it.first] = 0;
                pq.push({ -dis[it.first],it.first });
            }
            if (it.second + tdis == dis[it.first]) dp[it.first] = (dp[it.first] + dp[tpos]) % (int(1e9) + 9);
        }
    }
    printf("%d", dp[e]);
    return 0;
}