题目描述
解析
先上一张样例的图>_<
对图进行宽度优先搜索（bfs），可以得到一个搜索树。把1当作根节点，定义这棵搜索树中与根节点距离相同（即边数相同）的点属于同一层。对于一个点x，距离比少一条边的点都是它的上一层。如上图中相同颜色属于相同层，不同颜色属于不同层。由于是无向无权图，bfs搜索树的层数就是该节点的最短路径。每一层的节点都由它的上一层拓展而来，于是可以知道某个结点x的最短路径总数等于上一层中所有能够到达x的节点的最短路径总数之和。令dp[x]表示1到x的最短路径树，则dp[x]=
∑
i
\displaystyle\sum_{i}
i∑dp[
y
i
y_{i}
yi],
y
i
y_{i}
yi是x上一层中所有与x相连的点（此处有点dp的思想，由于是逐层扩展，所以满足了dp的无后效性）。具体实现：bfs遍历图的过程中，用vis[x]记录点x的层数（假设根节点的层数为1，vis数组初始化为0），由点u扩展到一个未访问过的v点时，v层数更新为vis[u]+1。假如u的出边v已经访问过且它是v的下一层，则dp[v]+=dp[u]。在bfs遍历时逐层更新dp数组就可以得到答案。另外，自环对于最短路没有影响可以不储存。而重边和其它边对最短路径数的影响是一样的，不用做特别处理。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std
;
const int maxM
=2e6+10; / /最大边数
const int maxN
=1e6+10; / /最大点数
const int mod
=100003;
struct edge
{
int u
;
int v
;
int w
;
int next
;
}e
[maxM
]; / /链式前向星存图
int head
[maxM
];
int vis
[maxN
]; / /记录点的层数，vis
[x
]表示x的层数，vis
[x
]为
0表示x未被访问
int dp
[maxN
]; / /dp
[x
]表示点
1到x的最短路径数
int cnt
=0; / /统计边数
void insert(int u
,int v
){ / /链式前向星存图的加边函数
cnt
++;
e
[cnt
].u
=u
;
e
[cnt
].v
=v
;
e
[cnt
].next
=head
[u
];
head
[u
]=cnt
;
}
queue
<int>que
;
void bfs(int cur
){ / /bfs的过程中更新dp数组
vis
[cur
]=1; / /标记已访问
que
.push(cur
); / /将
1入队
while(!que
.empty()){
int u
=que
.front();
que
.pop();
for(int i
=head
[u
];i
>0;i
=e
[i
].next
){
if(!vis
[e
[i
].v
]){ / /u的出边v没有访问过的话，节点入队，更新节点层数vis
[]和最短路径数dp
[]
que
.push(e
[i
].v
);
vis
[ e
[i
].v
]=vis
[u
]+1;
dp
[e
[i
].v
]+=dp
[u
]%mod
;
}
else if(vis
[e
[i
].v
]==vis
[u
]+1) / /已经访问过且u是v的上一层时更新最短路径数dp
[]
dp
[e
[i
].v
]+=dp
[u
]%mod
;
}
}
}
int main(){
memset(head
,-1,sizeof(head
));
memset(vis
,0,sizeof(vis
));
memset(dp
,0,sizeof(dp
));
int N
,M
;
scanf("%d%d",&N
,&M
);
for(int i
=1;i
<=M
;i
++){ / /读入边
int u
,v
;
scanf("%d%d",&u
,&v
);
if(u
!=v
) { / /细节：自环对于最短路没有影响可以不储存
insert(u
,v
); / /注意无向图要存两遍
insert(v
,u
);
}
}
dp
[1]=1;
bfs(1);
for(int i
=1;i
<=N
;i
++) printf("%d\n",dp
[i
]%mod
);
return 0;
}
