【算法】最短路计数（搜索）复习

题目

给出一个?N?个顶点?M?条边的无向无权图，顶点编号为?1?到?N。

问从顶点?1?开始，到其他每个点的最短路有几条。

输入格式

第一行包含?2?个正整数?N,M，为图的顶点数与边数。

接下来?M?行，每行两个正整数?x,y，表示有一条顶点?x?连向顶点?y?的边，请注意可能有自环与重边。

输出格式

输出?N?行，每行一个非负整数，第?i?行输出从顶点?1?到顶点?i?有多少条不同的最短路，由于答案有可能会很大，你只需要输出对?100003?取模后的结果即可。

如果无法到达顶点?i?则输出?0。

数据范围

1≤N≤1e5
1≤M≤2e5

输入样例：

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例：

1
1
1
2
4

思路

?变量介绍：

?从点1出发，开始搜索设每条边的长度为1。

=========================================================================?

如果从点 t 到达点 u?时，所走的路径长度小于dist[ u?]，则进行

将点 u?的cnt[ u?] 更新为cnt[ t ]，dist[ u ] 更新为 dist[ t ] + 1。

=========================================================================?

如果从点 t 到达点 u 时，所走的路径长度等于 dist[ u ]，则进行

将cnt[t] 加到 cnt[u] 上面。

=========================================================================

如果从点 t 到达点 u 时，所走的路径长度大于 dist[ u ]，则不进行任何操作。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100100, M = 4 * N;
int n,m;
int h[N],ne[M],e[M],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b)
{
    ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
}

void bfs()
{
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    cnt[1] = 1;
    dist[1] = 0;
    q.push(1);
    st[1] = true;
    while(!q.empty())
    {
        int t = q.front();
        st[t] = false;
        q.pop();
        for(int i = h[t]; ~i; i = ne[i])
        {
            int u = e[i];
            if(dist[u] > dist[t] + 1)
            {
                dist[u] = dist[t] + 1;
                cnt[u] = cnt[t];
                cnt[u] %= 100003;
                if(!st[u]) q.push(u);
            }
            else if(dist[u] == dist[t] + 1)
            {
                cnt[u] += cnt[t];
                cnt[u] %= 100003;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m --)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    bfs();
    for(int i = 1; i <= n; i ++) printf("%d\n",cnt[i]);
    return 0;
}

难度：中等

时/空限制：1s / 64MB

总通过数：6250

总尝试数：11237

来源：《信息学奥赛一本通》

算法标签 最短路???????方案数

题目来自：?1134. 最短路计数 - AcWing题库