【模板】Floyd

特别暴力的最短路问题

算法思路

假如 a->b = 12 ， a->c=55 ， b->c=3。 那么，我们想要 a->c 那肯定就是借助b节点走过去要好一点。 同理，其他的节点也可以这样走，我们就实现了从每个节点之间最短的路径了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+12,inf=1e9+12;
int dis[N][N],u,v,w,n,m;
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
     {
       if( i==j ) continue;
     dis[i][j]=inf;
     }
  }
  while(m--)
  {
    cin>>u>>v>>w;
    if( !dis[u][v] ) dis[u][v]=w;
    dis[u][v]=min(dis[u][v],w);
  }
  for(int k=1;k<=n;k++)
  {
    for(int i=1;i<=n;i++)
    {
      if( i==k ) continue;
      for(int j=1;j<=n;j++)
      {
        if( j==i or j==k ) continue;
        if( !dis[i][j] ) dis[i][j]=dis[i][k]+dis[k][j];
        dis[i][j]=min( dis[i][j],dis[i][k]+dis[k][j]  );

      }
    }
  }
  for(int i=1;i<=n;i++)
  {
    cout<<dis[1][i]<<" ";
  }

}