GESP 八级 · GESP 202509 C++ 八级 第 15 题

下面的程序使用出边邻接表表达的带权无向图，则从顶点 0 到顶点 3 的最短距离为（ ）。

#include <vector>
using namespace std;
class Edge {
public:
    int dest;
    int weight;
    Edge(int d, int w) : dest(d), weight(w) {}
};
class Graph {
private:
    int num_vertex;
    vector<vector<Edge>> vve;
public:
    Graph(int v) : num_vertex(v), vve(v) {}
    void addEdge(int s, int d, int w) {
        vve[s].emplace_back(d, w);
        vve[d].emplace_back(s, w);
    }
};
int main() {
    Graph g(4);
    g.addEdge(0, 1, 8);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 3);
    g.addEdge(2, 3, 7);
    return 0;
}

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】图算法｜Dijkstra 单源最短路｜优先队列松弛

1. 🎯 考纲定位

本题核心考察《GESP 大纲》八级模块中的“图算法”考点，命题人特意用邻接表实现带权无向图，卡住的是大多数考生对 Dijkstra 算法收敛条件的理解——很多人只背“松弛操作”公式，却忽略“优先队列弹出即确定最短”的本质，导致在复杂路径选择上判断失误。