codevs 1077 多源最短路 flyod 弗洛伊德算法

目录

1. 输入描述
2. 输出描述
3. 样例

题目描述

已知n个点(n<=100)，给你n*n的方阵，a[i,j]表示从第i个点到第j个点的直接距离。

现在有Q个询问，每个询问两个正整数，a和b，让你求a到b之间的最短路程。

满足a[i,j]=a[j,i];

输入描述

第一行一个正整数n，接下来n行每行n个正整数，满足a[i,i]=0,再一行一个Q，接下来Q行，每行两个正整数a和b。

输出描述

一共Q行，每行一个整数。

样例

输入
3
0 1 1
1 0 3
1 3 0
1
2 3

输出
2

#include <iostream>
using namespace std;

int mp[102][102];

int main() {
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mp[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (j != k) {
					mp[j][k] = min(mp[j][k], mp[j][i] + mp[i][k]);
				}
			}
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int i, j;
		cin >> i >> j;
		cout << mp[i-1][j-1] << endl;
	}
}