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

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

int weight[4][4] = {
    {0, 5, 8, 10},
    {5, 0, 1, 7},
    {8, 1, 0, 3},
    {10, 7, 3, 0}
};

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】最短路径算法｜邻接矩阵｜Dijkstra算法

1. 🎯 考纲定位

本题锁定在 GESP 八级"算法"模块的图论最短路径考点。命题人刻意在直达路径（0→3=10）和间接路径（0→1→2→3=9）之间制造认知冲突，卡住只会看直接边、不会枚举中转点的考生——这是八级图论最典型的陷阱设计。