if(d[i,k]+d[k,j]==d[i,j]) 頂點k在i到j的最短路上。
#include<stdio.h>
#define min(a,b) (a<b?a:b)
#define maxint 200000000
int main()
{
long g[101][101]={0},d[101][101],n,m,a,b,p,i,j,k,ans;
scanf("%ld%ld",&n,&m);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
d[i][j]=maxint;
g[i][j]=maxint;
}
for(i=1;i<=m;i++)
{
scanf("%ld%ld",&a,&b);
g[a][b]=1;
g[b][a]=1;
d[a][b]=1;
d[b][a]=1;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(k!=i && i!=j && j!=k)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
scanf("%ld",&p);
for(i=1;i<=p;i++)
{
ans=2;
scanf("%ld%ld",&a,&b);
for(j=1;j<=n;j++)
if(a!=j && d[a][j]+d[j][b]==d[a][b])
ans++;
printf("%ld\n",ans);
}
}
posted on 2010-01-06 19:20
lee1r 閱讀(183)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論