题解：AcWing 6054 最短路径问题

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6054. 最短路径问题 - AcWing题库【题目描述】平面上有n nn个点每个点的坐标均在− 10000 ∼ 10000 -10000\sim 10000−10000∼10000之间。其中的一些点之间有连线。若有连线则表示可从一个点到达另一个点即两点间有通路通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。【输入】共n m 3 nm3nm3行其中:第一行为整数n nn。第2 22行到第n 1 n1n1行共n nn行每行两个整数x xx和y yy描述了一个点的坐标。第n 2 n2n2行为一个整数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#【代码详解】#includebits/stdc.husingnamespacestd;#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;// 边的两个端点cinn;// 输入顶点数// 输入每个顶点的坐标for(inti1;in;i){cinver[i].xver[i].y;}cinm;// 输入边数// 输入每条边for(inti1;im;i){cinft;// 输入边的两个端点edge[f][t]edge[t][f]getDis(ver[f],ver[t]);// 无向图存储距离}cinstte;// 输入起点和终点}// Floyd-Warshall算法voidfloyd(){// 初始化距离矩阵memset(dis,0x43,sizeof(dis));// 使用0x43填充使dis中每个元素的值大约为1.08e16// 初始化直接相连的边for(inti1;in;i){for(intj1;jn;j){if(edge[i][j]0)// 如果有边{dis[i][j]edge[i][j];}}}// 对角线置0自己到自己的距离为0for(inti1;in;i){dis[i][i]0;}// Floyd算法核心动态规划for(intk1;kn;k)// 中间点{for(inti1;in;i)// 起点{for(intj1;jn;j)// 终点{if(dis[i][j]dis[i][k]dis[k][j])// 松弛操作{dis[i][j]dis[i][k]dis[k][j];}}}}}intmain(){init();// 初始化floyd();// 执行Floyd算法coutfixedsetprecision(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