[Vijos1446] 最短路上的统计

2014-11-07
竞赛题解 / 图论
Vijos最短路

描述 Description

一个无向图上，没有自环，所有边的权值均为 1，对于一个点对（a,b）, 我们要把所有 a 与 b 之间所有最短路上的点的总个数输出。

输入格式 InputFormat

第一行 n,m, 表示 n 个点，m 条边
接下来 m 行，每行两个数 a,b, 表示 a,b 之间有条边
在下来一个数 p, 表示问题的个数
接下来 p 行，每行两个数 a,b, 表示询问 a,b

输出格式 OutputFormat

对于每个询问，输出一个数 c, 表示 a,b 之间最短路上点的总个数

样例输入 SampleInput

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4

样例输出 SampleOutput

4
3
2

Vijos 1446

代码 Code

Floyd. 每次枚举每个点判断是不是在最短路上。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=105;
int i,j,t,n,m,l,r,k,z,y,x;
int dis[maxn][maxn];
int p,ans;
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) dis[i][j]=inf;
    for (i=1;i<=m;i++) scanf("%d%d",&x,&y),dis[y][x]=dis[x][y]=1;
    for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    scanf("%d",&p);
    for (i=1;i<=p;i++)
    {
        ans=0;
        scanf("%d%d",&x,&y);
        for (j=1;j<=n;j++) if (dis[x][j]+dis[j][y]==dis[x][y] && x!=j && y!=j) ans++;
        ans+=2;
        printf("%d\n",ans);
    }
    return 0;
}