Geodetic集合

图G是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点，这些顶点的集合记作I(v, u)。

我们称集合I(v, u)为一个Geodetic集合。
例如下图中，I(2, 5)={2, 3, 4, 5}，I(1, 5)={1, 3, 5}，I(2, 4)={2, 4}。



给定一个图G和若干点对v,u，请你分别求出I(v, u)。

建一个边权值都为一的无相图，弗洛伊德算出最短路，然后再循环判断记录点就行了，没什么难度

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[50][50],n,m,t,v,u,dian[50][50][50],sum[50][50];
int main()
{
    memset(a,10,sizeof(a));
    memset(sum,0,sizeof(sum));
    memset(dian,0,sizeof(dian));
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[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(a[i][k]+a[k][j]<a[i][j])
                    a[i][j]=a[i][k]+a[k][j];
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][k]+a[k][j]==a[i][j])
                {
                    dian[i][j][++sum[i][j]]=k;
                }
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&v,&u);
        for(int j=1;j<=sum[v][u];j++)
        {
            cout<<dian[v][u][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}