辅导笔记(6):Floyed算法

#include<iostream>

#include <cmath>

#include<cstdio>

#include <bits/stdc++.h>

#define N 101

#define _for(i,a,b)  for(int i=(a);i<=(b);i++)

using namespace std;

struct point {

int x,y;

}p[N];

double g[N][N];

int main()

{

int n,i,j,k,m,a,b,s,t;

cin>>n; //n个点

_for(i,1,n)

  cin>>p[i].x>>p[i].y;

 

  _for(i,1,n)  //初始化图数组

    _for(j,1,n) {

    if(i==j)  g[i][j]=0;

    else g[i][j]=999999999;

  }

 

cin>>m;//m条边

_for(i,1,m) {

cin>>a>>b; //a,b两个点之间有直接关系

int d;

d=(p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y);

g[a][b]=g[b][a]=sqrt(d); //建立图关系

}

// _for(i,1,n) {  //输出 图数组

//     _for(j,1,n) {

//     cout<<g[i][j]<<"      ";

//     }

//     cout<<endl;

// }

//应用弗洛伊德算法

 

cin>>s>>t; //输入原点s,目标点t

_for(k,1,n)

  _for(i,1,n)

      _for(j,1,n)

        if(g[i][j]>g[i][k]+g[k][j])

          g[i][j]=g[i][k]+g[k][j];

printf("%.2lf",g[s][t]);

return 0;

}