本蒟蒻这个号的第一篇题解——最短路

本题的思路与题目名字一个样，就是求两点之间的最短路

可以用floyed， 我用的就是，其他算法我就不写了，绝对不是懒

可以理解像这样的一幅图（举个栗子）
|   y
| /  0
|1—x/

Copy

1为初始点，0为终点 那么此时， 很明显最短路是1>x>0 此时距离也就是x+sqrt(11+11),也就是约3.41。

简单点说就是，判断一个地方到另一个地方，是直接去快，还是多去一个换乘点更快

所以说是这段代码

void floyed(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);//g[i][j]表示从i到j的距离
//本句子表示说是从i到j短还是从i到k再到j短
			}
		}
	}
}

Copy

floyed写完了，输入与计算就不需要讲了，知道勾股定理吧，就用这个算。 完整代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=104;
int n,m,x,y,a[N],b[N];
double g[N][N];
void floyed(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);//g[i][j]表示从i到j的距离
//本句子表示说是从i到j短还是从i到k再到j短
			}
		}
	}
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}//输入
	cin>>m;
	memset(g,0x7f,sizeof g);
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		g[x][y]=g[y][x]=sqrt(pow(a[x]-a[y],2)+pow(b[x]-b[y],2));//勾股定理
	}
	floyed();
	cin>>x>>y;//问从x到y
	cout<<fixed<<setprecision(2)<<g[x][y];
	return 0;
}