当前位置: 代码迷 >> 综合 >> 最短路 floyd模板
  详细解决方案

最短路 floyd模板

热度:29   发布时间:2024-01-14 22:28:38.0

多源最短路 简单 但复杂度高 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>using namespace std;
typedef long long ll;
#define MAX 1005
#define inf 0x3f3f3f3f
int a[MAX][MAX];
int n;
void floyd()
{int i,j,k;for(k=1;k<=n;k++){for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(a[i][j] > a[i][k] + a[k][j])a[i][j] = a[i][k] + a[k][j];}}}
}
int main()
{int m,i,j;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j) a[i][i] = 0;else a[i][j] = inf;}}int u,v,w;for(i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);if(a[u][v] > w){a[u][v] = a[v][u] = w;}}scanf("%d%d",&u,&v);floyd();printf("%d\n",a[u][v]);return 0;
}