【图论】【最短路】最短路径问题-白红宇的个人博客

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

发布日期：2021-05-07 00:23:04 浏览次数：23 分类：技术文章

本文共 1616 字，大约阅读时间需要 5 分钟。

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

0 0

2 0

2 2

0 2

3 1

1 2

1 3

1 4

2 5

3 5

1 5

Sample Output

3.41

解题思路

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

Ford算法

未更新的为蓝点，更新过的为白点

d i s [1

5] = \infty

从 $1$ 出发， $1$ 标记为白点

d i s [1] = 0 ， d i s [2

5] = \infty

枚举所有的边

1

更新了

2 、 3 、 4

d i s [1] = 0 ， d i s [2] = 2 ， d i s [3] = 1 ， d i s [4] = 3 ， d i s [5] = \infty

在这里插入图片描述

再次枚举所有边，白点并不限制更新对象，既可以更新蓝点也可以更新白点

3

更新了

4

2

更新了

5

d i s [1] = 0 ， d i s [2] = 2 ， d i s [3] = 1 ， d i s [4] = 2 ， d i s [5] = 4

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

#include
   
    #include
    
     #include
     
      #include
      
       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

上一篇：【ybtoj】【luogu1073】【图论】【最短路】【SPFA】最优贸易

下一篇：【图论】【最短路】工厂的烦恼

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

Description

解题思路

发表评论

最新留言

关于作者

推荐文章