• for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
传递闭包
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]|=dp[i][k]&dp[k][j];
or
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
dp[i][j]=dp[i][k]|dp[k][j];
  • struct E{int v,w;};
bool operator <(E a,E b){return a.w>b.w;}
vector<E>g[N];
void dij(int s)
{
   for(int i=1;i<=n;i++)vis[i]=0,dis[i]=oo;
   priority_queue<E>dp;
   dis[s]=0;
   dp.push((E){s,0});
   while(!dp.empty())
   {
       E node=dp.top();
       dp.pop();
       int u=node.v;
       if(vis[u])continue;
       vis[u]=1;
       for(E e:g[u])
       {
           if(!vis[e.v] and dis[e.v]>dis[u]+e.w)
           {
               dis[e.v]=dis[u]+e.w;
               dp.push((E){e.v,dis[e.v]});
           }
       }
   }
}
  • int dis[N];
bool vis[N];
void spfa(int s){
  for(int i=1;i<N;i++)dis[i]=oo,vis[i]=true;
  dis[s]=0;
  queue<int>q;
  q.push(s);
  vis[s]=true;
  while(!q.empty()){
      int u=q.front();
      q.pop();
      vis[u]=true;
      for(int i=head[u];~i;i=g[i].next){
          int v=g[i].to;
          if(dis[u]+g[i].w<dis[v]){
              dis[v]=dis[u]+g[i].w;
              if(vis[v])q.push(v),vis[v]=false;
          }
      }
  }
}