这题本质上就是经典的朴素Dijkstra算法

使用

• G[MAXN][MAXN]邻接矩阵表示图
• vis[MAXN]表示点是否被标记
• dis[MAXN]表示源点到点i的最短距离
• pre[MAXN]表示点i的前向点

根据Dijkstra算法，进行迭代即可。

关于Dijkstra算法的理解，这里推荐一个视频：Dijkstra算法视频展示

这题的坑在于：有重边！

即可能出现多次输入点a和点b之间的路径权值，且每次输入权值不一样。

这时候就需要去重，取输入权值最小的一次即可，否则通过率只有33%

去重代码：

 G[x][y] = G[y][x] = min(w, G[x][y]);

 建议之后做题，使用邻接矩阵时，都进行去重。因为是否有重边不会在题目里面直接告诉你。有胜于无。

路径打印

本题中并未使用到前向点数组（pre[n]），部分题目会要求打印出过程路径，这时候就需要使用到前向数组来记录路径，并利用栈来进行打印输出。我在代码中加入了打印路径的函数printRoad(int s, int e)，补充完整了整个Dijkstra算法，所以以下代码很适合当做模板使用。

完整代码如下

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3F3F3F3F //无穷大
const int MAXN = 105;  //点的个数或数组的大小
int G[MAXN][MAXN];     //邻接矩阵法
int vis[MAXN];         //标记是否被标记
int dis[MAXN];         //原点到当前点的距离
int pre[MAXN];         //前向节点

void dijkstra(int s, int n) //s表示起点，n表示点的个数
{
    dis[s] = 0; //源点到自己的距离为0，需要手动先初始化。

    for (int i = 1; i <= n; i++)
    { //代表dijkstra的循...