题目如下⬇
多源最短路
** 时间限制: 1 s
** 空间限制: 128000 KB
题目描述 Description
已知n个点(n<=100)，给你n*n的方阵，a[i,j]表示从第i个点到第j个点的直接距离。
现在有Q个询问，每个询问两个正整数，a和b，让你求a到b之间的最短路程。
满足a[i,j]=a[j,i];
输入描述 Input Description
第一行一个正整数n，接下来n行每行n个正整数，满足a[i,i]=0,再一行一个Q，接下来Q行，每行两个正整数a和b。
输出描述 Output Description
一共Q行，每行一个整数。
样例输入 Sample Input
3
0 1 1
1 0 3
1 3 0
1
2 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
n<=100，Q可能非常大。g[i][j]均>=0
请使用flyod算法
可以自己想一想；
先上个图吧👇
无标题.png
这就是样例的图；
下面开始讲解弗洛伊德吧，让我们走进弗洛伊德算法的海洋😊
因为样例过于简单，不助于理解，才三个点所以我们换一个图👌
image.png
这就是一个图，图中的箭头就是方向，点就是节点。
对于一个图我们可以用邻接矩阵把他存起来如下所示
image.png
有的人会想不明白为什么会有0和一个奇怪的符号呢？看图中 1，1 ； 2，2 ； 3，3 ；4，4 都是0 我们可以知道由于自己和自己是没有路径的，我们就把自己到自己的
长度赋为0，那个奇怪的符号又是什么呢？看到 2，4 我们会发现 2 ，4是无法直接到达的，必须通过3；还有2，因为2是无法直接到1的，但1可以直接到2，所以在代码中我们可以用一个很大得数来表示这个奇怪的符号；
好了说了这么多，那么我们步入正题吧👱
image.png
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
那么如何求两点之间的最短路径呢？
image.png
我们定义
e[i][j]来表示是从i号顶点到j号顶点之间的路程
我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市（4->3）的路程e[4][3]原本是12。如果只通过1号城市中转（4->1->3），路程将缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城市到3号城市也可以通过2号城市中转，使得1号到3号城市的路程缩短为5（e[1][2]+e[2][3]=2+3=5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短；、
当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下
如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1n循环，j也是1n循环，代码实现如下。
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if ( e[i][j] > e[i][1]+e[1][j] )
e[i][j] = e[i][1]+e[1][j];
}
}
在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：
现在我们会发现有几个都变短了
接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小
在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：
通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。
经过两次
我们就会发现规律，这个算法就是把两个不相邻的点通过中间的的过渡点得到路径，然后不断刷新，直到所有的都更新完，也就是更新n次，就会得到最短路径；
下面请看代码↓
#include<iostream>
#define maxe 510
using namespace std;
int n;
int a[maxe][maxe],s,t,q;
int main() {
ios::sync_with_stdio(0);//这个可以加快cin的读入速度
cin >> n;//读入
int big = 1000000;//无穷大值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];//读入临界矩阵
}
}
//核心代码
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j&&j != k&&i != k) {
if (a[i][j] > a[i][k] + a[k][j])
a[i][j] = a[i][k] + a[k][j];
}
}
}
}
//
cin >> q;//读入访问数量
int x, y;
for (int i = 1; i <= q; i++) {
cin >> x >> y;
cout << a[x][y];//输出
}
return 0;
}
网友评论