洛谷P1144最短路计数题解

最短路计数

此题还是寻找从1到i点总共有几个最短路且每条边的边长为1，对于这种寻找最短路的个数，我们可以反向搜索，即先用(SPFA)预处理出所有点的最短路，然后我们反向记忆化搜索，可以用(sum[i])表示从i到1的最短路个数，然后我们初始化(sum[1] = 1)，然后就可以了

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define rqy 100003
using namespace std;
int n, m, lin[1000100], tot, dis[1000010], sum[1000010] = {0, 1}, vis[1000010];
queue <int> q;
struct cym{
    int to, next;
}e[1000100];
void add(int u,int v)
{
    e[++tot].to = v;
    e[tot].next = lin[u];
    lin[u] = tot;
}
int dfs(int u)//反向搜索 
{
    if (sum[u])
    return sum[u];
    for (int i = lin[u]; i; i = e[i].next)
      if (dis[u] == dis[e[i].to] + 1)
      sum[u] = (sum[u] + dfs(e[i].to)) % rqy;
    return sum[u];
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push(1);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (int i = lin[cur]; i; i = e[i].next)
        {
            if (dis[cur] + 1 < dis[e[i].to])
            {
                dis[e[i].to] = dis[cur] + 1;
                if (!vis[e[i].to])
                {
                    q.push(e[i].to);
                    vis[e[i].to] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    printf("%dn", dfs(i));
}