最短路计数
题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图,顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始,到其他每个点的最短路有几条。
输入格式
第一行包含 2 2 2 个正整数 N , M N,M N,M,为图的顶点数与边数。
接下来 M M M 行,每行 2 2 2 个正整数 x , y x,y x,y,表示有一条由顶点 x x x 连向顶点 y y y 的边,请注意可能有自环与重边。
输出格式
共 N N N 行,每行一个非负整数,第 i i i 行输出从顶点 1 1 1 到顶点 i i i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 i i i 则输出 0 0 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 1 1 到 5 5 5 的最短路有 4 4 4 条,分别为 2 2 2 条 1 → 2 → 4 → 5 1\to 2\to 4\to 5 1→2→4→5 和 2 2 2 条 1 → 3 → 4 → 5 1\to 3\to 4\to 5 1→3→4→5(由于 4 → 5 4\to 5 4→5 的边有 2 2 2 条)。
对于
20
%
20\%
20% 的数据,
1
≤
N
≤
100
1\le N \le 100
1≤N≤100;
对于
60
%
60\%
60% 的数据,
1
≤
N
≤
1
0
3
1\le N \le 10^3
1≤N≤103;
对于
100
%
100\%
100% 的数据,
1
≤
N
≤
1
0
6
1\le N\le10^6
1≤N≤106,
1
≤
M
≤
2
×
1
0
6
1\le M\le 2\times 10^6
1≤M≤2×106。文章来源:https://www.toymoban.com/news/detail-623811.html
#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.假设存在一条 𝑖 → 𝑗 的边。
若
d
i
s
i
+
1
<
d
i
s
j
,就令
d
i
s
j
=
d
i
s
i
+
1
,
c
n
t
j
=
c
n
t
i
;
若dis_i+1<dis_j,就令dis_j=dis_i+1,cnt_j=cnt_i;
若disi+1<disj,就令disj=disi+1,cntj=cnti;
若
d
i
s
i
+
1
=
d
i
s
j
,就令
c
n
t
j
+
=
c
n
t
i
若dis_i+1=dis_j,就令cnt_j+=cnt_i
若disi+1=disj,就令cntj+=cnti文章来源地址https://www.toymoban.com/news/detail-623811.html
到了这里,关于P1144 最短路计数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!