By Stockholm
最短路计数(Shortest Path Count)
来源：Luogu P1144 题目描述 给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1～N。问从 顶点 1 开始，到其他每个点的最短路有几条。 输入输出格式 输入格式： 输入第一行包含 2 个正整数 N，M，为图的顶点数与边数。 接下来 M 行，每行两个正整数 x, y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。 输出格式： 输出包括 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有 多少条不同的最短路，由于答案有可能会很大，你只需要输出 mod 100003 后的结果即可。如果无法到达顶点 i 则输出 0。输入输出样例 输入样例#1： 5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5 输出样例#1： 1 1 1 2 4 说明1 到 5 的最短路有 4 条， 分别为 2 条 1-2-4-5 和 2 条 1-3-4-5 （由于 4-5的边有 2 条）。 对于 20%的数据，N ≤ 100； 对于 60%的数据，N ≤ 1000； 对于 100%的数据，N<=1000000，M<=2000000。
思路
这个题用 SPFA 做，但是需要加一个计数操作，注意最后结果取模，以及如果一样的长度， 就需要在原来的基础上加上上一个节点累加器 中的记录数，SPFA 最好带上 SLF，这样快一些。
代码（C++）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
using namespace std;
int i,j,m,n;
int head[
1000001];
int us[
1000001];
int t[
1000001];
int dis[
1000001];
struct node
{
int yy;
struct node *nxt;
}a[
4000005];
int r()
{
int aans=
0;
char ch=getchar();
while(ch<
'0'||ch>
'9')
ch=getchar();
while(ch>=
'0'&&ch<=
'9')
{
aans*=
10;
aans+=ch-
'0';
ch=getchar();
}
return aans;
}
int spfa(
int x)
{
us[x]=
1;
deque<int>q;
dis[x]=
0;
q.push_front(x);
struct node *p;
while(!q.empty())
{
x=q.front();
p=&a[head[x]];
us[x]=
0;
q.pop_front();
while(p->yy!=
0)
{
if(dis[x]+
1<dis[p->yy])
{
t[p->yy]=t[x]%
100003;
dis[p->yy]=dis[x]+
1;
if(!us[p->yy])
{
if(q.empty()||dis[q.front()]>dis[p->yy])
q.push_front(p->yy);
else
q.push_back(p->yy);
us[p->yy]=
1;
}
}
else if(dis[x]+
1==dis[p->yy])
{t[p->yy]+=t[x];
t[p->yy]%=
100003;}
p=p->nxt;
}
}
}
int main()
{
n=r(),m=r();
int x,y;
for(i=
1;i<=m;i++)
{
x=r(),y=r();
a[
2*i-
1].yy=y;
a[
2*i-
1].nxt=&a[head[x]];
head[x]=
2*i-
1;
a[
2*i].yy=x;
a[
2*i].nxt=&a[head[y]];
head[y]=
2*i;
}
memset(dis,
0x7f7f7f7f,
sizeof(dis));
t[
1]=
1;
spfa(
1);
for(i=
1;i<=n;i++)
if(dis[i]!=
0x7f7f7f7f)
cout<<t[i]<<endl;
else
cout<<
0<<endl;
return 0;
}
