题目：https://www.luogu.org/problemnew/show/P1144
题意：问1到各个节点的最短路有多少条。
思路：如果松弛的时候发现是相等的，说明可以经过该点的最短路径到达当前点，也就是说最短路径变多了。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x3f3f3f3f 14 using namespace std; 15 typedef long long LL; 16 typedef pair<int, int> pr; 17 18 int n, m; 19 const int mod = 1e5 + 3; 20 const int maxn = 1e6 + 5; 21 const int maxm = 2e6 + 5; 22 int head[maxn]; 23 struct edge{ 24 int to, nxt; 25 }e[maxm * 2]; 26 int tot = 0; 27 28 void add(int x, int y) 29 { 30 e[++tot].to = y; 31 e[tot].nxt = head[x]; 32 head[x] = tot; 33 e[++tot].to = x; 34 e[tot].nxt = head[y]; 35 head[y] = tot; 36 } 37 38 struct cmp{ 39 bool operator()(const pr &a, const pr &b) 40 { 41 return a.first > b.first; 42 } 43 }; 44 45 int d[maxn], cnt[maxn]; 46 bool vis[maxn]; 47 void dijkstra() 48 { 49 memset(d, 0x3f, sizeof(d)); 50 priority_queue<pr>que; 51 vis[1] = true; 52 cnt[1] = 1; 53 d[1] = 0; 54 que.push(make_pair(d[1], 1)); 55 while(!que.empty()){ 56 pr now = que.top();que.pop(); 57 vis[now.second] = true; 58 for(int i = head[now.second]; i; i = e[i].nxt){ 59 if(d[e[i].to] > d[now.second] + 1){ 60 d[e[i].to] = d[now.second] + 1; 61 cnt[e[i].to] = cnt[now.second]; 62 que.push(make_pair(-d[e[i].to], e[i].to)); 63 } 64 else if(d[e[i].to] == d[now.second] + 1){ 65 cnt[e[i].to] = (cnt[e[i].to] + cnt[now.second]) % mod; 66 } 67 } 68 } 69 70 } 71 72 int main() 73 { 74 scanf("%d%d", &n, &m); 75 for(int i = 0; i < m; i++){ 76 int x, y; 77 scanf("%d%d", &x, &y); 78 add(x, y); 79 } 80 dijkstra(); 81 for(int i = 1; i <= n; i++){ 82 printf("%d ", cnt[i]); 83 } 84 }