2017-07-27 22:21:04
writer:pprp
该算法的本质是动态规划,形式简单,复杂度高为O(n^3);
d[i][j] = max(d[i][k]+d[k][j],d[i][j]);
采用的基本手段是松弛
适用:解决多源最短路径问题
代码如下:
#include <iostream>
using namespace std;
const int maxn = 200;
int n,s,t;
int a[maxn+1][maxn+1];
void init()
{
int m,u,v;
cin >> n >> m;
for(int i =1; i<=n; i++)
for(int j =1; j<=n; j++)
a[i][j] = -1;
for(int i = 1; i<=m; i++)
cin >> u >> v >> a[u][v];
cin >> s >> t;
}
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][k]!=-1&&a[k][j]!=-1)
a[i][j] = min(a[i][j],a[i][k]+a[k][j]);
}
}
int main()
{
init();
floyd();
cout << a[s][t]+a[t][s]<<endl;
return 0;
}
代码改变世界