最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

全球热头条丨AcWing1134/洛谷P1144 最短路计数

来源：博客园


(相关资料图)

AcWing传送门洛谷传送门

题目大意

\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\sim n\))的最短路数量

解题思路

\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)\(\qquad\)\(1.\)当\(dist_{\ j} < dist_{\ i} + 1\)的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge 必定没有i}\)，所以我们可以直接忽视这种情况\(\qquad\)\(2.\)当\(dist_{\ j} \ge dist_{\ i} + 1\)的时候，我们继续分成两类

\(\qquad \qquad \color{#0000ff}{\large a.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)\(\qquad\)\(\qquad\)在这种情况下，代表着\(i\)可以是\(1\sim j\)的最短路中的一个点，但是还有其它点，这里根据 加法原理就可以得出我们\(cnt_{\ j}\)应该加上\(cnt_{\ i}\)（因为从\(1\sim i\)的任意一条最短路，再加上\(i\sim j\)这条边，都属于\(1\sim j\)的最短路）。\(\qquad \qquad \color{#0000ff}{\large b.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)\(\qquad\)\(\qquad\)在这种情况下，代表\(i\)是目前第一个可以更新\(j\)的点，所以\(j\)是第一次被更新，需要入队，其它的操作和分类\(\color{#0000ff}{\large a}\)都是一样的

代码

#include #include #include using namespace std;const int N = 1e5 + 10, M = N << 2, mod = 1e5 + 3;int dist[N], n, m, cnt[N];int h[N], e[M], ne[M], idx;void add(int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void bfs() {    memset(dist, 0x3f, sizeof dist);    queue  q;        dist[1] = 0, cnt[1] = 1, q.push(1);        while (q.size())     {        auto t = q.front(); q.pop();                for (int i = h[t]; ~i; i = ne[i])         {            int j = e[i];            if (dist[j] > dist[t] + 1)            {                dist[j] = dist[t] + 1;                cnt[j] = cnt[t];                q.push(j);            }            else if (dist[j] == dist[t] + 1)                 cnt[j] = (cnt[j] + cnt[t]) % mod;        }    }}int main() {    scanf("%d%d", &n, &m);        memset(h, -1, sizeof h);    while (m -- )     {        int u, v;        scanf("%d%d", &u, &v);        add(u, v), add(v, u);    }        bfs();        for (int i = 1; i <= n; i ++ )         printf("%d\n", cnt[i]);        return 0;}

关键词： 都是一样的 加法原理 我们继续