Description
一个无向图上，没有自环，所有边的权值均为1，对于一个点对（a,b）,我们要把所有a与b之间所有最短路上的点的总个数输出。
Input
第一行n,m,表示n个点，m条边 接下来m行，每行两个数a,b,表示a,b之间有条边 在下来一个数p,表示问题的个数 接下来p行，每行两个数a,b,表示询问a,b
Output
对于每个询问，输出一个数c,表示a,b之间最短路上点的总个数
Sample Input
5 6 1 2 1 3 2 3 2 4 3 5 4 5 3 2 5 5 1 2 4 Sample Output
4 3 2 Hint
范围：n<=100，p<=5000
代码：
var
a:
array[
0..
200,
0..
200]
of longint;
n,m,z,x,y,i,j,k,sum:longint;
begin
readln(n,m);
for i:=
1 to n
do
for j:=
1 to n
do
a[i,j]:=
10000000;
for i:=
1 to m
do
begin
readln(x,y);
a[x,y]:=
1;
a[y,x]:=
1;
end;
for k:=
1 to n
do
for i:=
1 to n
do
for j:=
1 to n
do
if (i<>j)
and(i<>k)
and(j<>k)
then
if a[i,j]>a[i,k]+a[k,j]
then
begin
a[i,j]:=a[i,k]+a[k,j];
end;
readln(z);
for i:=
1 to z
do
begin
sum:=
0;
readln(x,y);
for j:=
1 to n
do
if a[x,j]+a[j,y]=a[x,y]
then
if (x<>j)
and(j<>y)
then
inc(sum);
writeln(sum+
2);
end;
end.
转载请注明原文地址: https://ju.6miu.com/read-968097.html
