阿宅日志——Floyd

阿宅日志——Floyd

图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)。
输入格式 Input Format
第一行两个整数n,m，分别表示图G的顶点数和边数（顶点编号1-n）下接m行，每行两个整数a,b表示顶点a和b之间有一条无向边。
第m+2行有一个整数k，表示给定的点对数。下接k行，每行两个整数v,u。
输出格式 Output Format
共k行，每行对应输入文件中每一个点对v,u，按顶点编号升序输出I(v, u)。同一行的每个数之间用空格分隔。
sample：
in：
5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4
out：
2 3 4 5
1 3 5
2 4

#include<stdio.h>
#include<stdlib.h>
int n, m, x, y, a[50][50], pre[50][50] = {0};
void floyd()//记录前驱节点
{int i , j , k;for(i = 1;i<=n;i++)for (j = 1; j <= n; j++)for (k = 1; k <= n; k++)if (a[i][k] && a[k][j]&&i!=j&&j!=k&&k!=i&& (a[i][j]>a[i][k] + a[k][j]||!pre[i][j])){pre[i][j] =pre[k][j];a[i][j] = a[i][k]+a[k][j];}
}
int main()
{ int k=0,i,t;memset(pre,0,sizeof(pre));scanf_s("%d%d",&n,&m);for (i = 1; i <= m; i++)//录入邻接矩阵{scanf_s("%d%d",&x,&y);a[x][y] = 1;a[y][x] = 1;pre[x][y] = x;pre[y][x] = y;}floyd();scanf_s("%d", &k);for (; k >= 1; k--)//k次询问{scanf_s("%d%d", &x, &y);//x起点 y终点if (x < y) { t = x; x = y; y = t; }//要求输出的序列最小 printf_s("%d ", y);for (; pre[x][y] != x; y = pre[x][y]) {printf_s("%d ", pre[x][y]);//system("pause");}printf_s("%d ", x);printf_s("n");}system("pause");return 0;
}