题解：AcWing 6054 最短路径问题

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：6054. 最短路径问题 - AcWing题库

【题目描述】

平面上有n nn个点，每个点的坐标均在− 10000 ∼ 10000 -10000\sim 10000−10000∼10000之间。

其中的一些点之间有连线。

若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。

现在的任务是找出从一点到另一点之间的最短路径。

【输入】

共n + m + 3 n+m+3n+m+3行，其中:

第一行为整数n nn。

第2 22行到第n + 1 n+1n+1行（共n nn行），每行两个整数x xx和y yy，描述了一个点的坐标。

第n + 2 n+2n+2行为一个整数m mm，表示图中连线的个数。

此后的m mm行，每行描述一条连线，由两个整数i ii和j jj组成，表示第i ii个点和第j jj个点之间有连线。

最后一行：两个整数s ss和t tt，分别表示源点和目标点。

点的编号为1 ∼ n 1\sim n1∼n。

【输出】

一行，一个实数（保留两位小数），表示从s ss到t tt的最短路径长度。

【输入样例】

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

【算法标签】

#Floyd#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineN105// 坐标结构体structCord{intx,y;// 坐标};doubleedge[N][N];// 邻接矩阵，存储边权intn,m;// n: 顶点数, m: 边数intst,te;// st: 起点, te: 终点doubledis[N][N];// dis[i][j]: 顶点i到顶点j的最短距离Cord ver[N];// 保存每个顶点的坐标// 计算两点间欧几里得距离doublegetDis(Cord a,Cord b){returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}// 初始化函数voidinit(){intf,t;// 边的两个端点cin>>n;// 输入顶点数// 输入每个顶点的坐标for(inti=1;i<=n;++i){cin>>ver[i].x>>ver[i].y;}cin>>m;// 输入边数// 输入每条边for(inti=1;i<=m;++i){cin>>f>>t;// 输入边的两个端点edge[f][t]=edge[t][f]=getDis(ver[f],ver[t]);// 无向图，存储距离}cin>>st>>te;// 输入起点和终点}// Floyd-Warshall算法voidfloyd(){// 初始化距离矩阵memset(dis,0x43,sizeof(dis));// 使用0x43填充，使dis中每个元素的值大约为1.08e16// 初始化直接相连的边for(inti=1;i<=n;++i){for(intj=1;j<=n;++j){if(edge[i][j]>0)// 如果有边{dis[i][j]=edge[i][j];}}}// 对角线置0（自己到自己的距离为0）for(inti=1;i<=n;++i){dis[i][i]=0;}// Floyd算法核心：动态规划for(intk=1;k<=n;++k)// 中间点{for(inti=1;i<=n;++i)// 起点{for(intj=1;j<=n;++j)// 终点{if(dis[i][j]>dis[i][k]+dis[k][j])// 松弛操作{dis[i][j]=dis[i][k]+dis[k][j];}}}}}intmain(){init();// 初始化floyd();// 执行Floyd算法cout<<fixed<<setprecision(2)<<dis[st][te];// 输出结果，保留2位小数return0;// 程序正常结束}

【运行结果】

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