P1144 最短路计数

最短路计数

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

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

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

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。

样例 #1

样例输入 #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\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据，$1\le N\le 100$；
对于 $60\%$ 的数据，$1\le N\le 10^3$；
对于 $100\%$ 的数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^6$。

#include<bits/stdc++.h>
using namespace std;
#define il inline
const int MAXN=2e6+5;
const int MOD=100003;
int n,m;
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
queue<int> q;
vector<int> nextpoints[MAXN];//bfs
il void bfs()
{memset(dis,0x3f3f,sizeof(dis));//初始化dis[1]=0;cnt[1]=1;vis[1]=1;q.push(1);while(!q.empty())//广搜{int x=q.front();q.pop();for(auto y:nextpoints[x]){if(!vis[y]){if(dis[x]+1<dis[y]){dis[y]=dis[x]+1;vis[y]=true;q.push(y);}//打标记，存更优}if(dis[x]+1==dis[y]){cnt[y]+=cnt[x];cnt[y]%=MOD;}}	}return;
}
// int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;nextpoints[u].push_back(v);nextpoints[v].push_back(u);}bfs();for(int i=1;i<=n;i++)cout<<cnt[i]<<endl;//输出答案return 0;
} 

ps:

单源最短路问题：
1.可以bfs的同时用cnt记录1~i的最短路径条数
2.假设存在一条 𝑖 → 𝑗 的边。
$若di{s}_i+1<di{s}_j，就令di{s}_j=di{s}_i+1，cn{t}_j=cn{t}_i；$
$若di{s}_i+1=di{s}_j，就令cn{t}_j+=cn{t}_i$