2176번: 합리적인 이동경로

https://www.acmicpc.net/problem/2176


$O(m\lg n)$

2번 정점을 시작 지점으로 다익스트라 알고리즘을 이용하면 거리가 최소인 지점을 차례대로 들를 수 있게 된다.
x번 정점을 탐색하고 있다면 x번보다 도착 지점(=2)에 가까운 거리의 정점에서 출발하는 경로 개수는 모두 구해놓았기 때문에 이를 이용하여 x번 정점에서 출발하는 경로 개수도 구할 수 있다.
답은 1번 정점에서 출발하는 경로 개수이다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, m, dp[1001], cst[1001];
vector<pair<int, int> > adj[1001];
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    fill(cst + 1, cst + 1 + n, 0x7fffffff);
    cst[2] = 0; dp[2] = 1;
    pq.push({ 0,2 });
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (cst[h] ^ dis) continue;
        for (auto it : adj[h]) {
            int tdis = it.second + dis;
            if (tdis < cst[it.first]) cst[it.first] = tdis, pq.push({ -tdis,it.first });
            if (cst[it.first] < dis) dp[h] += dp[it.first];
        }
    }
    printf("%d", dp[1]);
    return 0;
}