GESP 八级 · GESP 202409 C++ 八级 第 12 题

下列 Dijkstra 算法中，横线处应该填入的是（ ）。

#include <iostream>
using namespace std;

#define N 100
int n, e, s;
const int inf = 0x7fffffff;
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];
                }
            }
        }
    }
}

位运算：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（右移）。异或性质：a^a=0，a^0=a。

区分逻辑运算(&&,||,!)和位运算(&,|,~,!)。左移右移注意符号位的处理（算术右移vs逻辑右移）。负数的位运算要小心。

【考点】Dijkstra算法｜贪心策略｜数组遍历

🎯 考纲定位 本题是 GESP 八级图论算法的核心考点，命题人想卡住那些只背代码模板却不懂算法本质的学生。Dijkstra 在考纲八级图论模块属于必考内容，它要求考生不仅会套用模板，更要理解算法每一步的含义。

🧠 解题思维 看到这段 Dijkstra 代码，关键观察是内层循环要找的是"未访问且距离最小"的节点。因此条件必须同时满足 cheak[j]==0（未标记）和 dis[j]<minn（比当前最小值更小）——这是贪心策略的标准写法。外层循环执行 n 次，每次选出当前全局最小值作为下一轮起点，正是 Dijkstra 的核心流程。

🪤 陷阱拆解 A 选项 dis[j]>minn 会反向更新（找更大的），C 选项 >= 会重复更新相同距离的节点（浪费且可能出错），D 选项 !=0 会访问已确定节点（彻底破坏算法逻辑）。最阴险的是 C，很多人以为"相等也要更新"，其实 Dijkstra 中相等距离无需处理。cheak 数组未初始化是默认 0，这一点容易让粗心考生忽略。

🔄 反命题思维 如果把 dis[j]<minn 改成 <=，算法仍能跑通但效率下降；若改成 cheak[j]!=0，则变成 Bellman-Ford 的松弛逻辑，答案直接全错。记住：Dijkstra 的"找最小"永远是严格小于，这是它与 Bellman-Ford 最本质的区别。