洛谷1144 最短路计数

45 阅读 0 评论 30 点赞

我是靠谱客的博主神勇百褶裙，最近开发中收集的这篇文章主要介绍洛谷1144 最短路计数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

洛谷1144 最短路计数

本题地址： http://www.luogu.org/problem/show?pid=1144

题目描述

给出一个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

输出样例#1：

说明

1到5的最短路有4条，分别为2条1-2-4-5和2条1-3-4-5（由于4-5的边有2条）。
对于20%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 100000，M ≤ 200000。

【思路】

BFS。

图的边权为1，可以使用BFS。BFS拓展的时候如果遇到没有访问过的则cnt[v]=cnt[u]，如果遇到访问过而且d[v]==d[u]+1则将方案数累计入cnt[v]。

【代码】

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 using namespace std;
 6
 7 const int maxn = 1000000+10;
 8 const int MOD=100003;
 9 struct Edge{
10
int v,next;
11 }e[2*maxn];
12 int en,front[maxn];
13
14 int n,m;
15 int cnt[maxn];
16
17 inline int read_int() {
18
char c=getchar();
19
while(!isdigit(c)) c=getchar();
20
int x=0;
21
while(isdigit(c)) {
22
x=x*10+c-'0';
23
c=getchar();
24 
}
25
return x;
26 }
27 inline void AddEdge(int u,int v) {
28
en++;
29
e[en].v=v; e[en].next=front[u]; front[u]=en;
30 }
31
32 int vis[maxn],d[maxn];
33 void BFS() {
34
queue<int> q;
35
q.push(1); d[1]=1; cnt[1]=1; vis[1]=1;
36
while(!q.empty()) {
37
int u=q.front(); q.pop();
38
for(int i=front[u];i>=0;i=e[i].next) {
39
int v=e[i].v;
40
if(!vis[v]) {
41
vis[v]=1;
42
d[v]=d[u]+1;
43
cnt[v]=cnt[u];
44 
q.push(v);
45 
}
46
else
if(d[v]==d[u]+1){
47
cnt[v]=(cnt[u]+cnt[v])%MOD;
48 
}
49 
}
50 
}
51 }
52
53 int main() {
54
memset(front,-1,sizeof(front));
55
56
n=read_int() , m=read_int();
57
int u,v,w;
58
for(int i=1;i<=m;i++){
59
u=read_int(),v=read_int();
60 
AddEdge(u,v);
61 
AddEdge(v,u);
62 
}
63
64 
BFS();
65
66
for(int i=1;i<=n;i++) printf("%dn",cnt[i]);
67
return 0;
68 }