题目链接：城市间货物运输Ⅰ本篇学习了代码随想录Bellman_ford算法精讲，本题是经典的带负权值的单源最短路问题，Dijkstra求单源最短路问题的前提是图中的边无负权重。当图中的边存在负权重时，就需要使用Bellman_ford算法来进行求解了。Bellman_ford算法的核心思想是对

学习参考：代码随想录与Prim类似，当节点数目较多，边的数量很小的时候（稀疏图），可以考虑从边的角度来求最短路，邻接矩阵遇到稀疏图，会导致申请过大的二维数组造成空间浪费且遍历边的时候需要遍历整个n*n矩阵，造成时间浪费。这时使用邻接链表明显更加符合需求。而在朴素版Dijk