P1144-最短路计数

布满荆棘的人生 2023-06-01 08:55 13阅读 0赞

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 }

转载于:https://www.cnblogs.com/Asurudo/p/11518449.html