#include<iostream>
using namespace std;
int main()
{
int f[101][101],n,m,p,x,y,a[5000],b[5000],ans=0;

cin>>n>>m;

for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
f[i][j]=10000;//将距离定义得尽可能大

for(int i=1;i<=m;i++){
cin>>x>>y;
f[x][y]=f[y][x]=1;//无向图 据题意 距离为一
}

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];
} //floyd核心代码

cin>>p;
for(int i=1;i<=p;i++)
cin>>a[i]>>b[i];

for(int i=1;i<=p;i++){
for(int j=1;j<=n;j++)
if(a[i]!=j&&b[i]!=j)
if(f[a[i]][b[i]]==f[a[i]][j]+f[j][b[i]])//当走不同路径的步数都等于最小
ans++;//点数增加
cout<<ans+2<<endl;
ans=0;//重置
}

return 0;
}

var
n,m,x,y,p,i,j,k,ans:longint;
d:array[0..100,1..100,1..100]of longint;
map:array[1..100,1..100]of longint;
begin
read(n,m);
for i:=1 to n do
for j:=1 to n do
begin
if i=j
then map[i,j]:=0
else map[i,j]:=100000000;
end;
for i:=1 to m do
begin
read(x,y);
map[x,y]:=1;
map[y,x]:=1;
end;
for i:=1 to n do
for j:=1 to n do
d[0,i,j]:=map[i,j];
for k:=1 to n do
begin
for i:=1 to n do
for j:=1 to n do
begin
d[k,i,j]:=d[k-1,i,j];
if d[k,i,j]>d[k-1,i,k]+d[k-1,k,j]
then
d[k,i,j]:=d[k-1,i,k]+d[k-1,k,j];
end;
end;
read(p);
for i:=1 to p do
begin
ans:=0;
read(x,y);
for j:=1 to n do
if d[n,x,j]+d[n,j,y]=d[n,x,y]
then inc(ans);
writeln(ans);
end;
end.

floyed

program Project1;

var
ans, i, j, k, n, m, a, b, c: longint;
dist: array[1..100, 1..100] of longint;
begin
readln(n, m);
for i := 1 to n do
for j := 1 to n do
dist[i, j] := 200;
for i := 1 to m do
begin
readln(a, b);
dist[a, b] := 1;
dist[b, a] := 1;
end;
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
if dist[i, j] > dist[i, k] + dist[k, j] then
dist[i, j] := dist[i, k] + dist[k, j];
readln(c);
for i := 1 to c do
begin
readln(a, b);
ans := 2;
for j := 1 to n do
if dist[a, b] = dist[a, j] + dist[j, b] then
Inc(ans);
writeln(ans);
end;
end.

var n,m,a,b,k,i,j,p:integer;
f:array[1..100,1..100] of integer;
procedure floyd;
var i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if f[i,j]>f[i,k]+f[k,j] then f[i,j]:=f[i,k]+f[k,j];
end;
procedure find(x,y:integer);
var i,c:integer;
begin
c:=0;
for i:=1 to n do
if f[x,y]=f[x,i]+f[i,y] then inc(c);
writeln(c+2);
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
f[i,j]:=10000;
for i:=1 to m do
begin
readln(a,b);
f[a,b]:=1;
f[b,a]:=1;
end;
floyd;
readln(p);
for i:=1 to p do
begin
readln(a,b);
find(a,b);
end;
end.

#include<stdio.h>
#include<string.h>
int d[111],map[111][111];
int min(int a,int b)
{
if(a>b)return b;
else return a;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int i,j;
int max=100000;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)map[i][j]=0;
else map[i][j]=max;
}
}
for(i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x-1][y-1]=1;
map[y-1][x-1]=1;
}
int k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
}
int q;
scanf("%d",&q);
int ans[q];
memset(ans,0,sizeof(ans));
int a,b;
for(i=0;i<q;i++)
{
scanf("%d%d",&a,&b);
for(j=0;j<n;j++)
if(map[a-1][j]!=max&&map[j][b-1]!=max&&map[a-1][b-1]==map[a-1][j]+map[j][b-1])ans[i]++;
}
for(i=0;i<q;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
floyd求最短路

#include<iostream>
using namespace std;
int main()
{
int f[101][101],n,m,p,x,y,a[5000],b[5000],ans=0;
cin>>n>>m;
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
f[i][j]=10000;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
f[x][y]=f[y][x]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(f[i][j]>f[i][k]+f[k][j])
f[i][j]=f[i][k]+f[k][j];
cin>>p;
for(int i=1;i<=p;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=p;i++)
{
for(int j=1;j<=n;j++)
if(a[i]!=j&&b[i]!=j)
if(f[a[i]][b[i]]==f[a[i]][j]+f[j][b[i]])
ans=ans+1;
cout<<ans+2<<endl;
ans=0;
}
return 0;
}

AC了但不懂
既然每条边权值为一，那么点的个数不应该是最短路权值+1吗？？
难道所有最短路上的点都要算上。。。？？？
附AC代码：
#include <stdio.h>
#include <iostream>
using namespace std;

int n,m,xw,map[101][101];

int main(){
cin>>n>>m;
int i,j,k;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
map[i][j]=1000000;

}
for(i=1;i<=m;++i){
int x,y;
cin>>x>>y;
map[x][y]=1;
map[y][x]=1;

}
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}
cin>>xw;
for(i=1;i<=xw;++i){
int a,b;
cin>>a>>b;
int sum=2;
for(j=1;j<=n;++j)
if(map[a][b]==map[a][j]+map[j][b]&&j!=a&&j!=b) sum++;

cout<<sum<<endl;

}
}

NOIP2014赛前AC留念
var k,j,a,b,i,m,n,p:longint;
f,cost:array[0..1000,0..1000] of longint;

function min(a,b:longint):longint;
begin
if a<b then exit(a)
else exit(b);
end;

function find(x,y:longint):longint;
var i:longint;
begin
find:=0;
for i:=1 to n do
if f[x,i]+f[i,y]=f[x,y] then find:=find+1;
end;

begin
readln(n,m);
for i:=1 to m do
begin
readln(a,b);
cost[a,b]:=1;
cost[b,a]:=1;
end;
readln(p);
for i:=1 to n do
for j:=1 to n do
if cost[i,j]<>0 then f[i,j]:=cost[i,j]
else f[i,j]:=1000000;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
f[i,j]:=min(f[i,k]+f[k,j],f[i,j]);
for i:=1 to p do
begin
readln(a,b);
writeln(find(a,b)+2);
end;
end.

var n,m,a,b,k,i,j,p:integer;
f:array[1..100,1..100] of integer;
procedure floyd;
var i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if f[i,j]>f[i,k]+f[k,j] then f[i,j]:=f[i,k]+f[k,j];
end;
procedure find(x,y:integer);
var i,c:integer;
begin
c:=0;
for i:=1 to n do
if f[x,y]=f[x,i]+f[i,y] then inc(c);
writeln(c+2);
end;

begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
f[i,j]:=10000;

for i:=1 to m do
begin
readln(a,b);
f[a,b]:=1;
f[b,a]:=1;
end;
floyd;
readln(p);
for i:=1 to p do
begin
readln(a,b);
find(a,b);
end;
end.

FLOYD求最短路的模板题， 作为初学者的我亦可水过。。。
思路就是：
Floyd求出最短路径。。
根据Floyd的性质 dis[i][j] == dis[i][k] + dis[k][j] && k != i && k != j 时 k点必在最短路上， 计数器+1
不过。。要注意这样找出的只是最短路中除起点终点以外点的个数，所以我们最后要将计数器 + 2。。。

代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1000000;
const int maxl = 150;
int n, m, from, to, q, x, y;
int dis[maxl][maxl];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) dis[i][j] = maxn;
for (int i = 1; i <= m; i ++)
{
scanf("%d%d", &from, &to);
dis[from][to] = dis[to][from] = 1;

}
scanf("%d", &q);
for (int k = 1; k <= n; k ++)
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}

for (int i = 1; i <= q; i ++)
{
int sum = 0;
scanf("%d%d", &x, &y);
for (int k = 1; k <= n; k ++)
{
if ((dis[x][y] == dis[x][k] + dis[k][y]) && (k != x) && (k != y))
sum ++;
}
printf("%d\n", sum + 2);
}
//system("pause");
return 0;
}

var
n,m,i,j,a,b,p,k,s:longint;
f:array[0..101,0..101] of int64;

begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
f[i,j]:=maxlongint;

for i:=1 to m do
begin
readln(a,b);
f[a,b]:=1; f[b,a]:=1;
end;

for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
begin
if (k=i) or (k=j) or (i=j) then continue;
if f[i,k]+f[k,j]<f[i,j] then f[i,j]:=f[i,k]+f[k,j];
end;

readln(p);
for i:=1 to p do
begin
s:=0;
readln(a,b);
for j:=1 to n do
if f[a,j]+f[j,b]=f[a,b] then inc(s);
writeln(s+2);
end;
end.