【图论】【最短路】最短路径问题

Description

平面上有n个点(N<=100)，每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点直线的距离。现在的任务是找出从一点到另一点之间的最短路径。

Input

输入文件short.in，共有n+m+3行，其中：
第一行为一个整数n。
第2行到第n+1行（共n行），每行的两个整数x和y，描述一个点的坐标(以一个空格隔开)。
第n+2行为一个整数m，表示图中的连线个数。
此后的m行，每行描述一条连线，由两个整数I,j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。

Output

输出文件short.out仅一行，一个实数(保留两位小数)，表示从S到T的最短路径的长度。

Sample Input

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

Sample Output

3.41

---

解题思路

最短路模板，输入的时候需要用公式 求出两个连接的点的距离（边权）

Ford算法
未更新的为蓝点，更新过的为白点
$dis[1$dis[1~$5]=∞$5]=∞

从$1$1出发，$1$1标记为白点
$dis[1]=0，dis[2$dis[1]=0，dis[2~$5]=∞$5]=∞

枚举所有的边
$1$1更新了$2、3、4$2、3、4
$dis[1]=0，dis[2]=2，dis[3]=1，dis[4]=3，dis[5]=∞$dis[1]=0，dis[2]=2，dis[3]=1，dis[4]=3，dis[5]=∞

再次枚举所有边，白点并不限制更新对象，既可以更新蓝点也可以更新白点
$3$3更新了$4$4
$2$2更新了$5$5
$dis[1]=0，dis[2]=2，dis[3]=1，dis[4]=2，dis[5]=4$dis[1]=0，dis[2]=2，dis[3]=1，dis[4]=2，dis[5]=4

至此，最短路就求完了（✿✿ヽ(°▽°)ノ✿）

---

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,S,T,x[2000],y[2000],lx[2000],ly[2000];
double s[2000],dis[2000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&lx[i],&ly[i]);
		s[i]=sqrt(pow(double(x[lx[i]]-x[ly[i]]),2)+pow(double(y[lx[i]]-y[ly[i]]),2));//求边权
	}
	scanf("%d%d",&S,&T);
	memset(dis,0x7f,sizeof(dis));
	dis[S]=0;//起点设为0
	for(int i=1;i<n;i++){//
		bool t=0;
		for(int j=1;j<=m;j++){
			if(dis[lx[j]]+s[j]<dis[ly[j]]){//
				dis[ly[j]]=dis[lx[j]]+s[j];//
				t=1;                       //
			}                              //判断这条边可不可以松弛连接的两点
			if(dis[ly[j]]+s[j]<dis[lx[j]]){//
				dis[lx[j]]=dis[ly[j]]+s[j];//
				t=1;
			} 
		}
		if(!t)break;//如果没有边可以松弛，就可以直接退出
	}
	printf("%.2lf",dis[T]);
}