单选题 适中
#20821

下面Floyd算法中,横线处应该填入的是( )。 # include <iostream> using namespace std ; # define N 2…

下面Floyd算法中,横线处应该填入的是( )。

#include <iostream>
using namespace std;

#define N 21
#define INF 99999999
int map[N][N];
int main() {
	int n, m, t1, t2, t3;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				map[i][j] = 0;
			else
				map[i][j] = INF;
		}
	}
	for (int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		map[t1][t2] = t3;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (__________) // 在此处填入选项
					map[i][j] = map[i][k] + map[k][j];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout.width(4);
			cout << map[i][j];
		}
		cout << endl;
	}
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

Floyd算法本质是个DP,或者可以理解为松弛操作:

i和j的最短路如果可以通过中间节点k做更新:

则需要map[i][j]>map[i][k]+map[k][j];选B。