关键字：BFS，递推。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
Input Format
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
Output Format
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
Sample Input #1
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
Sample Output #1
1
1
1
2
4
Hint
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。
由于边没有边权，所以点1到每一个点的最短路只需要用BFS就可以算出来了。BFS的过程中，如果从点x出发，碰到未入队的点y，那么count(y) = count(x)；如果y已入队，则需要distance(y) == distance(x)+1才可以count(y) += count(x)。
#include <stdio.h>
#define MOD 100003
int n,m;
int e[400010][2],p[100010];
int q[100010],dis[100010],cnt[100010],head,tail;
void adde(int sn,int fn,int id)
{
e[id][0] = fn; e[id][1] = p[sn]; p[sn] = id;
e[id+1][0] = sn; e[id+1][1] = p[fn]; p[fn] = id+1;
}
void bfs()
{
int i,sn,fn;
head = 1; tail = 2;
q[1] = 1; dis[1] = 1; cnt[1] = 1;
while(head<tail)
{
sn = q[head++];
for(i=p[sn];i;i=e[i][1])
{
fn = e[i][0];
if(dis[fn])
{
if(dis[fn] == dis[sn]+1) cnt[fn] = (cnt[fn]+cnt[sn])%MOD;
}
else
{
dis[fn] = dis[sn]+1;
cnt[fn] = cnt[sn];
q[tail++] = fn;
}
}
}
}
int main()
{
int i,sn,fn;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&sn,&fn);
adde(sn,fn,i<<1);
}
bfs();
for(i=1;i<=n;i++) printf("%d\n",cnt[i]);
return 0;
}
2022年4月22日 18:05
Cleanliness is really a basic requirement that encourages good as well as healthy existence. But frequently, it demands more work than that which you can provide. A cleansing service helps to ensure that your way of life runs well with an increase of productivity as well as great defenses. However, you’ll run into various support companies that provide you cleansing services. It's really a difficult task to create a decision that's much better based in your requirements as well as preferences. Nicely, to help to make things easier for you personally, there tend to be prominent reasons why you need to consider availing the cleaning support from DIALAMAID. Read more to discover.