NOIP 提高 2015 第一轮 第 33 题：完善程序（双子序列最大和）第 2 空

题目

（最短路径问题）无向连通图 $G$ 有 $n$ 个结点，依次编号为 $0,1,2,\dots,(n-1)$。用邻接矩阵的形式给出每条边的边长，要求输出以结点 $0$ 为起点出发，到各结点的最短路径长度。

使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 $v$ 进行扩展，更新与 $v$ 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 $2$ 分，其余 $3$ 分）

#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v; int w[MAXV][MAXV]; // 邻接矩阵，记录边长 // 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1
int dist[MAXV]; int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展）
int main()
{
    cin >> n;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i++)
        dist[i] = -1;
    for (i = 0; i < n; i++)
        used[i] = 0;
    while (true) {
            (1)    ;
        for (i = 0; i < n; i++)
            if (used[i] != 1 && dist[i] != -1 && (v == -1 ||     (2)    ))
                    (3)    ;
        if (v == -1)
            break;
            (4)    ;
        for (i = 0; i < n; i++)
            if (w[v][i] != -1 && (dist[i] == -1 ||     (5)    ))
                dist[i] = dist[v] + w[v][i];
    }
    for (i = 0; i < n; i++)
        cout << dist[i] << endl;
    return 0;
}

第 2 空应填（ ）

答案

dist[i]<dist[v]

题解

考点定位

本题（Dijkstra 第②空）考「最小 dist 筛选」,对应大纲 4.3.3 Dijkstra（难度【3】）。

解题过程

②处在未扩展、已可达的点中筛最小：

``cpp dist[i] < dist[v] ``

答案：dist[i]<dist[v]。

易错提醒

① 条件含 used[i]!=1 && dist[i]!=-1（可达才参与）；② 贪心：最小 dist 的未扩展点已定型。