[网络协议]SSL 1613 最短路问题

题目描述：

有 $N$ 个点$(N<100)$，给出每个点的直角系坐标，某些点之间有双向变相连，边权为坐标上两点的直线距离，现在给出你原点和目标点，让你求两点间的最短路（保留两位小数）。

样例输入：

5
0 0 
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5

样例输出：

3.41

解题思路：

典型的最短路问题，由于$N$ 太小了，我们可以用任何算法随便搞。这里来介绍$Floyed$ 算法。

$Floyed$ 算法是应用了动态规划思想，用来求多源最短路问题（如问任意 $i$ 到 $j$ 的最短路），时间复杂度为 $\Theta (n^3)$ ，适用于小于 200 的数据。

此算法的核心思想是：
考虑枚举第 $k$ 个点，判断在 $i$ 和 $j$ 的最短路中是否需要进过点 $k$。此时设 $di{s}_{i,j}$ 表示从 $i$ 到 $j$ 的最短路，那么若这条路径中需要经过 $k$ 点，则显然 $di{s}_{i,j}=di{s}_{i,k}+di{s}_{k,j}$。因此，我们不断考虑中介点，尝试使 $di{s}_{i,j}$ 不断变优，也就是不断尝试松弛操作，最终 $di{s}_{i,j}$ 即为所求。

	for(int k=1;k<=n;k++)  //枚举中介点
	  {
	  	for(int i=1;i<=n;i++)  //枚举起点
	  	  {
	  	  	for(int j=1;j<=n;j++)  //枚举终点
	  	  	  {
	  	  	  	if(dis[i][j]>dis[i][k]+dis[k][j])  //判断经过 k 点是否会使路径更优
	  	  	  	  dis[i][j]=dis[i][k]+dis[k][j];  //松弛
			  } 
		  }
	  }

CODE：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,x[110],y[110];
double f[110][110];
double dis(int a,int b)
{
	return sqrt((abs(x[a]-x[b])*abs(x[a]-x[b]))+(abs(y[a]-y[b])*abs(y[a]-y[b])));
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	int a,b;
	cin>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    f[i][j]=1e8;  //初始化
	for(int i=1;i<=m;i++)
	  {
	  	cin>>a>>b;
	  	f[a][b]=dis(a,b);
	  	f[b][a]=f[a][b];
	  }
	for(int k=1;k<=n;k++)
	  {
	  	for(int i=1;i<=n;i++)
	  	  {
	  	  	for(int j=1;j<=n;j++)
	  	  	  {
	  	  	  	if(f[i][j]>f[i][k]+f[k][j])
	  	  	  	  f[i][j]=f[i][k]+f[k][j];
			  } 
		  }
	  }
	cin>>a>>b;
	printf("%.2f",f[a][b]);
	return 0;
}