P1144-最短路计数-蒲公英云

P1144-最短路计数

1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 4 #define INF 1000000003
 5 #define ll long long
 6 
 7 using namespace std;
 8 
 9 const int maxn = 2000003;
10 inline ll read()
11 {
12     ll ans = 0;
13     char ch = getchar(), last = ' ';
14     while(!isdigit(ch)) last = ch, ch = getchar();
15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
16     if(last == '-') ans = -ans;
17     return ans;
18 }
19 inline void write(ll x)
20 {
21     if(x < 0) x = -x, putchar('-');
22     if(x >= 10) write(x / 10);
23     putchar(x % 10 + '0');
24 }
25 struct edge
26 {
27     ll to;
28     ll cost;
29 };
30 vector<edge> G[maxn];
31 
32 ll V,E,B;
33 
34 typedef pair<ll,ll> P;//first 是最短距离，second 是顶点编号 
35 ll d[maxn];
36 ll t[maxn];
37 ll ans[maxn];
38 void shortest_path(int s)
39 {
40     priority_queue<P,vector<P>,greater<P>> que;
41     
42     _for(i,1,V+1)
43         d[i] = INF;
44     d[s] = 0;
45     ans[s] = 1;
46     que.push(P{
    0,s});
47 
48     while(!que.empty())
49     {
50         P p = que.top();que.pop();
51         int v = p.second;
52         if(d[v] < p.first) continue;
53 
54         _for(i,0,G[v].size())
55         {
56             edge e = G[v][i];
57             if(d[e.to] > d[v] + e.cost)
58             {
59                 d[e.to] = d[v] + e.cost;
60                 que.push(P{d[e.to],e.to});
61             }
62             if(d[e.to] == d[v] + e.cost)
63             {
64                 ans[e.to] += ans[v];
65                 ans[e.to] %= 100003;
66             }
67         }
68     }
69 }
70 
71 int main()
72 {
73     V = read(),E = read();
74 
75     _for(i,0,E)
76     {
77         ll s,t,c;
78         s = read(),t = read(),c = 1;
79         //  scanf("%d %d %d",&s,&t,&c);
80         G[s].push_back(edge{t,c});
81         G[t].push_back(edge{s,c});
82     }
83     shortest_path(1);
84     _for(i,1,V+1)
85         printf("%d\n",ans[i]);
86     return 0;
87 }