spfa模板

用于带负权边的图
不能用于有负权环的图
一般题（单源点最短路的题）用dijkstra
*时间复杂度 O(KM) //k表示每个点平均入队次数,M表示边数 //出题人卡它很容易，可以把它卡成O(N^2) //不能用于棋盘格子，会被卡爆 *

int dis[N],vis[N];
void spfa(int s){
  memeset(dis,0x3f,sizeof(dis));
  queue<int>q;
  q.push(s);
  dis[s]=0;
  vis[s]=1;//vis数组表示s点是否在队列q中，而不是表示是否访问过
  while(!q.empty()){
    int u=q.front();q.pop();
    vis[u]=0;
    for(int i=head[u];i;i=edge[i].next){
      if(dis[u]+edge[i].len <dis[edge[i].a]){
        dis[edge[i].a]=dis[u]+edge[i].len ;
        if(vis[edge[i].a]) continue;
        q.push(edge[i].a);
        vis[edge[i].a]=1;
      }
    }
  }
}