最短路总结

void relax(int i,int j,int k){
  if(dis[k]>dis[i]+j)
    dis[k]=dis[i]+j;
}

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

void Bellman_ford(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  for(int i=1;i<n;++i)
    for(int j=1;j<=m;++j)
      relax(Edge[j].u,Edge[j].w,Edge[j].v);
}

queue<int> q;
void SPFA(int s){
  memset(dis,inf,sizeof(dis));
  q.push(s);
  vis[s]=1;
  dis[s]=0;
  while(!q.empty()){
    const int u=q.front();
    q.pop();
    vis[u]=0;
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(dis[v]>dis[u]+w[e]){
        dis[v]=dis[u]+w[e];
        if(!vis[v]) q.push(v),vis[v]=1;
      }
    }
  }
}

void Dijkstra(int s){
  memset(dis,inf,sizeof(dis));
  dis[s]=0;
  for(int i=1;i<=n;++i){
    int maxs=inf,u=0;
    for(int j=1;j<=n;++j)
      if(!vis[j]&&dis[j]<maxs)
        u=j,maxs=dis[j];
    vis[u]=1;
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      if(!vis[v]&&dis[v]>dis[u]+w[e]) dis[v]=dis[u]+w[e];
    }
  }
}

//对于一个DAG可以得知它的拓扑序，从而通过DP解决问题
queue<int> q;
int DAG_shortest_path(){
  memset(dis,inf,sizeof(dis));
  for(int i=1;i<=n;++i)
    if(degree[i]==0) q.push(i);
  while(!q.empty()){
    const int u=q.front();
    q.pop();
    topo[++topo[0]]=u;
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      --degree[v];
      if(degree[v]==0) q.push(v);
    }
  }
  ans=inf;
  for(int i=1;i<=topo[0];++i){
    const int u=topo[i];
    for(int e=pre[u];e;e=nx[e]){
      const int v=to[e];
      dis[v]=min(dis[v],dis[u]+w[e]);
    }
    ans=min(ans,dis[u]);
  }
  return ans;
}