Floyd题解

#include<bits/stdc++.h>//头文件
using namespace std;//定义名字空间
const int N=1100;//常量N表示m的范围
int n,m,s,t;//定义部分
int a,b;
double f[N][N];//f[i][j]表示从i点到j点的最短距离
double x[N],y[N];//x,y数组记录每一个店的x坐标和y坐标
int main(){
	cin>>n;//输入
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=2000000222;//初始化f数组为极大值
		}
	}
	for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];//输入每家店的坐标
    }
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		f[a][b]=sqrt(pow((x[a]-x[b]),2)+pow((y[a]-y[b]),2));
		f[b][a]=sqrt(pow((x[a]-x[b]),2)+pow((y[a]-y[b]),2));
        //因为是无向图,所以两条边都要记录
        //两点之间的距离公式为,L=根号(平方(x坐标差)+平方(y坐标差))
	}
	cin>>s>>t;//输入起点和终点
	for(int k=1;k<=n;k++){//外层是中转点
		for(int i=1;i<=n;i++){//中层是起点
			for(int j=1;j<=n;j++){//内层是终点
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                //进行松弛操作
			}
		}
	}//弗洛伊德核心代码
	printf("%.2lf",f[s][t]);//保留两位小数点输出从起点到终点的最短距离
	return 0;
}