目录二、本题代码三、关键思路四、优化原因五、注意事项// 展示完整题目二、本题代码// 展示完整代码三、关键思路1、用队列把当前遍历节点所指向的节点记录到队列里更新在队列里的松弛有意义的节点的最短距离四、优化原因1、因为单纯的Bellman_ford算法会进行很多次无意义的松弛比如一开始的时候只有起点1所指向的节点能更新最短距离但是第一条输入的边是5 6 -2这个时候起点1和结点5根本就没有相连所以就算进行了一次循环也不会做任何操作就浪费了时间2、时间复杂度更低五、注意事项1、邻接表在定义的时候要先写好数组的位置个数2、邻接表在加入结构体的时候要push_back(结构体名(成员变量1,成员变量2))// 注意这个结构体名要写出来