最短路径----floyed

多元最短路径

思路:

遍历全数组，看每个点是否可以松弛，如果可以，将松弛完与未松弛进行比较，取值最小的方式。

          时间复杂度O(n³)

Code:

#include<iostream>
#include<cmath>
#include<memory.h>
using namespace std;
int main()
{
    int a[100][100]; 
    int n,p,q;
    memset(a,0xffff,sizeof(a));//给每条边都赋值为无穷大
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p>>q;
        cin>>a[p][q];
    }
    for(int i=1;i<=n;i++)
    a[i][i]=0;//自己到自己的距离为0
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    a[i][j]=min(a[i][k]+a[k][j],a[i][j]);//判断k是否可以松弛，以及松弛后的大小
        cout<<a[n][m]<<endl;
    return 0;
 }