【图论】最短路模板

SPFA:

inline void spfa(int x){
  memset(dis,0x3f,sizeof(dis));
  memset(vis,0,sizeof(vis));
  dis[x]=0;vis[x]=true;
  Q.push(x);
  while(!Q.empty()){
    int u=Q.front();Q.pop();
    vis[u]=false;
    for(int i=head[u];i;i=edge[i].nxt){
      int v=edge[i].to;
      int w=edge[i].w;
      if(dis[v]>dis[u]+w){
        dis[v]=dis[u]+w;
        if(!vis[v]){
          Q.push(v);
          vis[v]=true;
        }
      }
    }  
  }
}

Dijkstra(堆优化）:

inline void Dijkstra(int x){
  memset(dis,0x3f,sizeof(dis));
  memset(vis,0,sizeof(vis));
  dis[x]=0;
  Q.push(make_pair(0,x));
  while(!Q.empty()){
    int u=Q.top().second;Q.pop();
    if(vis[u]) continue;
    vis[u]=true;
    for(int i=head[u];i;i=edge[i].nxt){
      int v=edge[i].to;
      int w=edge[i].w;
      if(dis[v]>dis[u]+w){
        dis[v]=dis[u]+w;
        q.push(make_pair(-dis[v],v));
      }
    }
  }
}

Floyd

inline void Floyd(){
  for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

自己默写的，应该没什么问题吧