JDOJ 1523: VIJOS-P1446 最短路上的统计

JDOJ传送门

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

题解：

一看是任意两点之间的最短路，并且n<=100。那么就可以果断地用Floyd算法了。

如果还没有学习Floyd算法，请移步至我的最短路算法的讲解。

最短路算法讲解

那么现在不是简单地让我们求任意两点最短路，而是要我们统计最短路点的个数。

这样的话怎么处理呢?

先跑最短路，然后我们继续用Floyd思想，枚举断点，如果这个端点在最短路上，那么一定有：这个点到最短路两个端点的距离和等于这个最短路的长度。

真相大白。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,p,ans;

int map[110][110];

int main()

{

    scanf("%d%d",&n,&m);

    memset(map,0x3f,sizeof(map));

    for(int i=1;i<=n;i++)

        map[i][i]=0;

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        map[x][y]=map[y][x]=1;

    }

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                map[i][j]=min(map[i][k]+map[k][j],map[i][j]);

    scanf("%d",&p);

    while(p--)

    {

        ans=0;

        int a,b;

        scanf("%d%d",&a,&b);

        for(int k=1;k<=n;k++)

            if(map[a][k]+map[k][b]==map[a][b] || map[b][k]+map[k][a]==map[a][b])

                ans++;

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

VIJOS-P1446 最短路上的统计