最短路（SPFA版）

欢迎在评论区留言和订阅专栏！

最短路有很多种解决方案，如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);
    val[s]=true;
    
    while(!q.empty()){
    	int t= q.front();
        q.pop();
        
        val[t]=fa