洛谷 P1144 最短路计数

传送门：https://www.luogu.org/problemnew/show/P1144

这虽然是一道普及+的题，然而我发现我现在还没做过，这也就直接导致我今天模拟T2只杠了个暴力分……

那这道题怎么做呢？既然是最短路，那么一定要用spfa或dijkstra了，这里就讲dijkstra的做法吧，主要是这比spfa简单点，而且spfa不是那啥了吗。

众所周知，在那个所谓的什么松弛操作的时候，如果dis[u] + c[u->v] < dis[v]，我们就更新dis[v]，这时候从u过来的路径，就可能是到v的最短路，所以到v的最短路条数num[v] = num[u];而另一种情况是dis[u] + c[u->v] == dis[v]时，那么num[v] += num[u]了。嗯，完事了

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter printf("\n")

 #define space printf(" ")

 #define Mem(a) memset(a, 0, sizeof(a))

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const int eps = 1e-;

 const int maxn = 1e6 + ;

 const int mod = ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch))

     {

         ans = ans *  + ch - ''; ch = getchar();

     }

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 int n, m;

 vector<int> v[maxn];

 #define pr pair<int, int>

 #define mp make_pair

 priority_queue<pr, vector<pr>, greater<pr> > q;

 int dis[maxn], num[maxn];

 bool done[maxn];

 void dijkstra(int s)

 {

     for(int i = ; i <= n; ++i) dis[i] = INF;

     dis[s] = ; num[s] = ;

     q.push(mp(dis[], s));

     while(!q.empty())

     {

         int now = q.top().second; q.pop();

         if(done[now]) continue;

         done[now] = ;

         for(int i = ; i < (int)v[now].size(); ++i)

         {

             if(dis[now] +  < dis[v[now][i]])        //此题边权都是1

             {

                 dis[v[now][i]] = dis[now] + ;

                 num[v[now][i]] = num[now];

                 q.push(mp(dis[v[now][i]], v[now][i]));

             }

             else if(dis[now] +  == dis[v[now][i]]) num[v[now][i]] = (num[v[now][i]] + num[now]) % mod;

         }

     }

 }

 int main()

 {

     n = read(); m = read();

     for(int i = ; i <= m; ++i)

     {

         int x = read(), y = read();

         v[x].push_back(y); v[y].push_back(x);

     }

     dijkstra();

     for(int i = ; i <= n; ++i) {write(num[i]); enter;}

     return ;

 }

巴特西

洛谷 P1144 最短路计数

最新文章

热门文章