单选题 适中
#20820

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

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

#include <iostream>
using namespace std;

#define N 100
int n, e, s;
const int inf = 0x7fffff;
int dis[N + 1];
int cheak[N + 1];
int graph[N + 1][N + 1];
int main() {
	for (int i = 1; i <= N; i++)
		dis[i] = inf;
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}
	cin >> s;
	dis[s] = 0;
	for (int i = 1; i <= n; i++) {
		int minn = inf, minx;
		for (int j = 1; j <= n; j++) {
			if (__________) { // 在此处填入选项
				minn = dis[j];
				minx = j;
			}
		}
		cheak[minx] = 1;
		for (int j = 1; j <= n; j++) {
			if (graph[minx][j] > 0) {
				if (minn + graph[minx][j] < dis[j]) {
					dis[j] = minn + graph[minx][j];
				}
			}
		}
	}
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

朴素dijkstra算法,在非负权图中,用cheak[]标记已经求得最短路的点(因为已经求得,所以后续不会再更新),每次选择距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx,由非负权图的原因,该节点minxj将加入已经求得最短路的点的集合,同时用minx尝试是否能更新S到其他待球节点的最短路。横线处就是求解距离起点S的未求得最短路(cheak[]==0)的,且最近的节点minx的,因此选B。