题解 P1144 【最短路计数】

· · 题解

我第一眼看见最短路计数其实是一头雾水

但是我们可以再想一想，只要起点到一个点的距离有几种不同走法但是所过路径权值和相等就说明到这个点的最短路种数不同

也就是说，要求A到B的最短路的方案数，也就是说求A到B有多少条路径是最短且总权值相等的

我们如何解决这个问题呢？

根据最短路算法的方式，他是根据前面点最短路的情况来决定后面点的情况的。

那么如果我们要求当前点的方案数，我们就需要分两种情况 第一种是到当前点的最短路需要更新：

那么就要根据松弛操作里的：

if (dis[a[k].to]>dis[v]+a[k].dis)
                dis[a[k].to]=dis[v]+a[k].dis;

当前的方案数也就是中间点v的方案数

第二种就是当前的到B的最短路不需要更新，即出现

dis[a[k].to]=dis[v]+a[k].dis

由于出现了与之前中间点不同的最短路相同的情况，则到当前B点的方案数加上这个中间点的方案数

注意：第一种情况的改变是通过替换，第二种情况是累加！

其他的都是一样的，根据SPFA的模板套一下即可 感慨：这种根据前驱来决定当前的思想真的很实用也很重要啊！

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
struct CZP
{
    int next,to,dis;
}a[5000001];
int b[1000001],h[1000001],dis[1000001],k,n,m,sx,top,que[100001],tot[1000001];
void cun(int from,int to,int dis)
{
    a[++top].next=h[from];
    a[top].to=to;
    a[top].dis=dis;
    h[from]=top;
}  //邻接表存储
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    h[i]=-1;
    tot[1]=1;
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d",&x,&y);
        cun(x,y,1);
        cun(y,x,1);
    }  //无向图存储
    for (int i=1;i<=n;i++)
    dis[i]=2147483647;
    dis[1]=0;
    b[1]=1;
    int head=0,tail=1;
    que[tail]=1;
    do
    {
        head=head%100000+1;  //循环队列存储
        int v=que[head];
        k=h[v];
        b[v]=0;
        while (k!=-1)
        {
            if (dis[a[k].to]>dis[v]+a[k].dis)
            {
                dis[a[k].to]=dis[v]+a[k].dis;
                tot[a[k].to]=tot[v];  //出现第一种情况，即最短路出现更短的需要新更新的情况
                if (!b[a[k].to])
                {
                    b[a[k].to]=1;
                    tail=tail%100000+1;
                    que[tail]=a[k].to;
                }
            }
            else
            if (dis[a[k].to]==dis[v]+a[k].dis)  //出现第二种情况，即为出现与到当前点最短路相同的但中间点选取不同的情况
            {
                tot[a[k].to]+=tot[v];
                tot[a[k].to]%=100003;  //注意题目要求的取模
            } 
            k=a[k].next;
        }
    }while (head<tail);
    for (int i=1;i<=n;i++)
        printf("%d\n",tot[i]);   //输出即可
    return 0;
 }

Ps：可能思路有雷同，但是我也是很用心写了啊，管理员辛苦了！