题解 P1144 【最短路计数】

· · 题解

在练单源最短路，突然写到这道题，再加上瞥见讨论，想都没想直接敲SPFA。

但是之后一想，裸的最短路虽然可以记录最短路径，但他只能记录一条，与题意要求不符。之后想可以先SPFA处理起点到各点的最短距离，之后再用BFS遍历整个图。但最后想到既然每条边权值为1，可以直接用BFS，第一次到某个点的路径即是最短路径，这样同时也得到了最短路径的长度。

具体实现：从起点出发，BFS遍历，每到一个点，若之前未访问过，就标记，当前到它的最短路径条数即为该路径上他的父节点的条数；否则比较从当前路径走所得到的与起点的距离和最短路径大小，（此时最短路径大小已知，见上文）若相等，它的最短路径条数加上该路径上它父节点路径数 。起点到某一点最短路路径条数等于起点到它所有父节点路径条数的和。讲的有些赘余，代码思路比较清晰，可以参考，如果还不懂可以画一下样例： 从起点开始走，每到一个点就标记，并标上它到起点的最短距离和它的路径数，直到遍历全图。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define Mod 100003
#define maxn 1000005
#define maxm 2000005
#define maxx 2000005
using namespace std;
int n,m,head[maxn],k=0,flag[maxn],d[maxn];//head[i]存的是编号为i的节点出发的第一条边，flag[i]记录起点到i最短路径条数，d[i]存的是起点到i的最短路长度。
inline void read(int &x){//最简练的快读，因为读入不存在负数，所以不必特判
    char c;
    while(!isdigit(c=getchar()));//isdigit判断所读是否为数字
    x=c-'0';
    while(isdigit(c=getchar()))
      x=x*10+c-'0';
}
struct Edge{//前向星存图（若没接触过，自行百度）
    int to,next;
}e[maxm<<1];//无向边，每条边正反存两遍
inline void add_edge(int x,int y){//加边
    e[++k].to=y;
    e[k].next=head[x];
    head[x]=k;
}
queue<int>q;//存的是节点
int main(){
    read(n);read(m);
    int x,y;
    for(int i=1;i<=m;i++){//建图
        read(x);read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    for(int i=1;i<=n;i++)//初始化
      d[i]=maxx;
    d[1]=0;
    q.push(1);//将起点压入队列
    flag[1]=1;//起点到起点的最短路为1，见样例
    while(!q.empty()){//简单的BFS
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(d[v]<d[u]) continue;//防止这个点下一次遍历它的父节点，发生死循环
            if(!flag[v]){//如果未标记过
                flag[v]=flag[u];//处理路径条数
                d[v]=d[u]+1;//处理最短路
                q.push(v);//压入队列
            }
            else{
                if(d[u]+1==d[v])//判断是否为最短路径
                  flag[v]+=flag[u];
                  flag[v]%=Mod;//记得要%，第一次交没%，wa了一个，T了一个（不知道为什么会T）
            }
//            for(int i=1;i<=n;i++)
//                  cout<<flag[i]<<" ";cout<<"\n";//虽不是最后的结果，但此输出对理解题意十分重要
        }
    }
    for(int i=1;i<=n;i++)
      cout<<flag[i]<<"\n";
    return 0;
}