最短路有很多种解决方案,如SPFA、Floyd、Dijstra、A*等。接下来我就介绍SPFA。 1.简介 SPFA是一种用BFS来求最短路的解决方案,与 Dijstra、A*一样。总体步骤只有一个:bfs。 2.代码 1.bfs /*变量等定义我省略了,只显示核心代码,欢迎在评论区打出这里的代码!*/ void bfs(){ queue<int> q; bool val[100005]; int dis[100005]; for (int i = 1; i <= n; i++) { dis[i]=1e9; } dis[s] = 0;//s为初始节点 q.push(s); v...