题目描述 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
1.Floyd算法的简介
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
2.Floyd的算法流程
按照题目要求，读入数据到3x3的邻接矩阵内

Y0JP04PDS_WO6}M1P2%EY)H.png

input.png

最后，根据题意要求，直接找到最短路径位置输出即可。
具体实现代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int e[1100][1100], k, i, j, n; int a, b;
int inf = 99999999;//用inf(infinity的缩写)存储一个我们认为的正无穷值   
int main() {
    //n*n的矩阵 
    scanf("%d", &n);
    //初始化   
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j) e[i][j] = 0;
            else e[i][j] = inf;
            //读入邻接矩阵信息
            for (i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    cin >> e[i][j];
            }
            //Floyd-Warshall算法核心语句   （生成最小路径图）
            for (k = 0; k < n; k++)//附加顶点（1=n）遍历，判断哪个路径短
                for (i =0; i < n; i++)
                    for (j = 0; j < n; j++)
                        if (e[i][j]>e[i][k] + e[k][j])//选择最小值
                            e[i][j] = e[i][k] + e[k][j];//更新较小节点
            //输出最终的结果
            int q;
            cin >> q;
            int s, t;
            for (int i = 1; i <= q; i++) {
                cin >> s >> t;//输入欲查找的最短路径的位置
                printf("%d\n", e[s-1][t-1]);
            }
            return 0;
}