【최단로】로곡P1144최단로계수(프로세스 모델링 문제 주의)

제목.
LP1144
사고의 방향
정상적인 최단길은 덮어쓸 수 있는 최단거리 개수를 검출하고 경로가 같은 최단거리 개수를 검출하면 된다.본 문제는 과정 모델링 문제에 주의해야 한다. 프로그램 과정에서 제때에 모델링을 해야 한다. 출력할 때가 되면 다시 하지 마라. 그렇지 않으면 터질지 안 터질지 아무도 모른다.
코드

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define _for(i,a,b) for(int i = a; i
#define _rep(i,a,b) for(int i = a; i<=b; i++)
using namespace std;

const int INF = 2000000 + 1000;
const int maxn = 1000000 + 10;
const int MOD = 100003;
int n, m, d[maxn], c[maxn];
bool done[maxn];
vector<int> G[maxn];

struct HeapNode {
    int u, d;
    bool operator < (const struct HeapNode& rhs) const {
        return d>rhs.d;
    }
    HeapNode(int u, int d) :u(u), d(d) {};
};

void dijkstra(int s) {
    priority_queue q;
    HeapNode first(s, 0);
    q.push(first);
    _rep(i, 1, n) d[i] = INF;
    d[s] = 0; c[s] = 1;
    while (!q.empty()) {
        HeapNode now = q.top(); q.pop();
        int u = now.u;
        if (done[u]) continue;
        done[u] = true;
        _for(i, 0, G[u].size()) {
            int v = G[u][i];
            if (!done[v] && d[u] + 1 <= d[v]) {
                if (d[u] + 1 < d[v]) {
                    d[v] = d[u] + 1;
                    c[v] = c[u];
                    HeapNode nn(v, d[v]);
                    q.push(nn);
                }
                else {
                    c[v] += c[u];
                    c[v] %= MOD;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    _for(i, 0, m) {
        scanf("%d%d", &u, &v);
        if (u == v) continue;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dijkstra(1);
    _rep(i, 1, n) printf("%d
", c[i]);

    return 0;
}