# [模板] 最短路计数

## 思路

$$dis[v] > dis[x] + w$$

$$num[x] = num[v]$$

$$dis[v] = dis[x] + w$$

$$num[x] \leftarrow num[x] + num[v]$$

## Luogu-1144 最短路计数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define P pair<int, int>

using namespace std;
const int MAXN = 1000000 + 10;
const int MAXM = 4000000 + 10;
const int MOD = 100003;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int Head[MAXN], to[MAXM], Next[MAXM], w[MAXM], tot = 1;
int dis[MAXN], num[MAXN];
int n, m;
bool vis[MAXN];

priority_queue<P, vector<P>, greater<P> >que;

inline void dij(int start){
memset(dis, 0x3f, sizeof(dis));

dis[start] = 0;
num[start] = 1;
que.push(make_pair(0, start));

while(!que.empty()){
P front = que.top();
que.pop();

if(vis[front.second])
continue;

int x = front.second;
vis[x] = true;

int v = to[i];

if(dis[v] > dis[x] + w[i]){
dis[v] = dis[x] + w[i];
num[v] = num[x];

que.push(make_pair(dis[v], v));
}else if(dis[v] == dis[x] + w[i]){
num[v] += num[x];
num[v] %= MOD;
}
}
}
}

inline void add(int a, int b, int c){
to[tot] = b;
w[tot] = c;
}

int main(){

for(register int i=1; i<=m; i++){