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

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

---

解题思路

最短路模板

dijkstra算法
蓝白点思想，未确定的点为蓝点，确定的点为白点。
$dis$dis为起点到每个点的最短路。
从蓝点中找到目前最短路的点，把TA变为白点，再以这个点为出发点更新与TA相连的蓝点。

$1$1为起点，$dis[1]=0$dis[1]=0，$dis[2$dis[2~$n]=∞$n]=∞

更新和$1$1相连的点，$dis[1]=0$dis[1]=0，$dis[2]=2$dis[2]=2，$dis[3]=4$dis[3]=4，$dis[4]=7$dis[4]=7，$dis[5]=∞$dis[5]=∞

在蓝点中找到最短的点——$2$2，更新与$2$2相连的点
$dis[1]=0$dis[1]=0，$dis[2]=2$dis[2]=2，$dis[3]=3$dis[3]=3，$dis[4]=7$dis[4]=7，$dis[5]=4$dis[5]=4

不停做下去
…
…
…
$dis[1]=0$dis[1]=0，$dis[2]=2$dis[2]=2，$dis[3]=3$dis[3]=3，$dis[4]=4$dis[4]=4，$dis[5]=4$dis[5]=4

于是，从$1$1到每个点的最短路都求出来啦

---

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double maxn=0x7fffffff;
double dis[200],a[200][200];
int n,m,x[200],y[200],S,T,v[200];
void dijkstra(){
	memset(dis,0x7f,sizeof(dis));
	dis[S]=0;
	while(1){//好吧，其实这里是for(int i=1;i<=n;i++)
		double minn=maxn;
		int k=0;
		for(int j=1;j<=n;j++)
		    if(!v[j]&&dis[j]<minn){//找到最短的蓝点
		    	minn=dis[j];
		    	k=j;
		    }
		if(k==0)break;//这里不需要这句的
		v[k]=1;//标记为白点
		for(int j=1;j<=n;j++)
		    if(!v[j])
		       dis[j]=min(dis[j],dis[k]+a[j][k]);//更新与k相连的点
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m); 
	memset(a,0x7f,sizeof(a));//路径一开始也要赋成无穷大
	for(int k=1;k<=m;k++){
		int i,j;
		scanf("%d%d",&i,&j);
	    a[i][j]=sqrt((abs(x[i]-x[j]))*(abs(x[i]-x[j]))+(abs(y[i]-y[j]))*(abs(y[i]-y[j]))),a[j][i]=a[i][j];
	    //公式我抄的，欢迎复制
	}
	scanf("%d%d",&S,&T);
	dijkstra();
	printf("%0.2lf",dis[T]);
}