本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1744 采购特价商品 - 洛谷【题目描述】中山路店山店海成了购物狂爱与愁大神的“不归之路”。中山路上有n nnn ≤ 100 n \leq 100n≤100家店每家店的坐标均在− 10000 -10000−10000至10000 1000010000之间。其中的m mm家店之间有通路。若有通路则表示可以从一家店走到另一家店通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗【输入】共n m 3 nm3nm3行第一行整数n nn。接下来n nn行每行两个整数x xx和y yy描述了一家店的坐标。接下来一行整数m mm。接下来m mm行每行描述一条通路由两个整数i ii和j jj组成表示第i ii家店和第j jj家店之间有通路。接下来一行两个整数s ss和t tt分别表示原点和目标店。【输出】仅一行一个实数保留两位小数表示从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【核心思想】问题分析给定n nn家店的平面坐标( x i , y i ) (x_i, y_i)(xi,yi)和m mm条无向通路每条通路的边权为两点间的欧几里得距离。求从起点s ss到终点t tt的最短路径长度。这是一个多源最短路径问题由于n ≤ 100 n \leq 100n≤100规模较小适合使用Floyd-Warshall算法直接求出所有点对之间的最短距离。算法选择Floyd-Warshall 算法通过动态规划思想枚举中间点k kk逐步松弛所有点对之间的最短距离欧几里得距离直接通路的边权由坐标通过( x i − x j ) 2 ( y i − y j ) 2 \sqrt{(x_i-x_j)^2 (y_i-y_j)^2}(xi−xj)2(yi−yj)2计算关键步骤初始化读取n nn店铺数、n nn个坐标( x i , y i ) (x_i, y_i)(xi,yi)、m mm通路数建图读取m mm条通路( u , v ) (u, v)(u,v)建立无向邻接矩阵g [ u ] [ v ] g [ v ] [ u ] 1 g[u][v] g[v][u] 1g[u][v]g[v][u]1初始化距离矩阵d p [ i ] [ j ] dp[i][j]dp[i][j]d p [ i ] [ i ] 0 dp[i][i] 0dp[i][i]0自己到自己为0 00若g [ i ] [ j ] 1 g[i][j] 1g[i][j]1则d p [ i ] [ j ] c a l c ( i , j ) dp[i][j] calc(i, j)dp[i][j]calc(i,j)欧几里得距离其余d p [ i ] [ j ] ∞ dp[i][j] \inftydp[i][j]∞不可达Floyd 三重循环松弛枚举中间点k kk1 11到n nn枚举起点i ii1 11到n nn枚举终点j jj1 11到n nn松弛操作若d p [ i ] [ j ] d p [ i ] [ k ] d p [ k ] [ j ] dp[i][j] dp[i][k] dp[k][j]dp[i][j]dp[i][k]dp[k][j]则更新d p [ i ] [ j ] d p [ i ] [ k ] d p [ k ] [ j ] dp[i][j] dp[i][k] dp[k][j]dp[i][j]dp[i][k]dp[k][j]输出答案d p [ s ] [ t ] dp[s][t]dp[s][t]保留两位小数时间/空间复杂度时间复杂度O ( n 3 ) O(n^3)O(n3)三重循环n ≤ 100 n \leq 100n≤100时完全可接受空间复杂度O ( n 2 ) O(n^2)O(n2)存储d p dpdp距离矩阵Floyd 的核心思想动态规划思想d p [ k ] [ i ] [ j ] dp[k][i][j]dp[k][i][j]表示仅使用前k kk个节点作为中间点时i ii到j jj的最短距离通过滚动数组优化为d p [ i ] [ j ] dp[i][j]dp[i][j]松弛原理最短路径的子路径也是最短路径若i → j i \to ji→j经过k kk更短则更新全源最短路径一次计算即可得到任意两点间的最短距离适合频繁查询场景适用场景节点数n ≤ 500 n \leq 500n≤500的稠密图全源最短路径问题或需要多次查询不同起点终点的场景【算法标签】#普及 #Floyd【代码详解】#includebits/stdc.husingnamespacestd;constintN105;// 最大店铺数量intn,m,st,ed;// n: 店铺数量, m: 通路数量, st: 起点, ed: 终点intx[N],y[N];// x[i], y[i]: 第i家店的坐标doubledp[N][N];// dp[i][j]: 从店铺i到店铺j的最短距离Floyd算法intg[N][N];// g[i][j]: 邻接矩阵g[i][j]1表示i和j之间有通路// 计算两点之间的欧几里得距离直线距离doublecalc(inta,intb){returnsqrt((x[a]-x[b])*(x[a]-x[b])(y[a]-y[b])*(y[a]-y[b]));}intmain(){cinn;// 读入店铺数量// 读入每家店的坐标for(inti1;in;i)cinx[i]y[i];cinm;// 读入通路数量// 读入m条通路while(m--){intu,v;cinuv;g[u][v]1;// u和v之间有通路g[v][u]1;// 无向图双向建边}cinsted;// 读入起点和终点// 初始化Floyd距离矩阵for(inti1;in;i)for(intj1;jn;j)dp[i][j]1e9;// 初始化为无穷大表示不可达// 自己到自己的距离为0for(inti1;in;i)dp[i][i]0;// 对于直接有通路的店铺初始化距离为两点间的直线距离for(inti1;in;i)for(intj1;jn;j)if(g[i][j]1)dp[i][j]calc(i,j);// Floyd-Warshall算法求任意两点间的最短路径 // 枚举中间点kfor(intk1;kn;k){// 枚举起点ifor(inti1;in;i){// 枚举终点jfor(intj1;jn;j){// 松弛操作如果经过k点能缩短i到j的距离则更新if(dp[i][j]dp[i][k]dp[k][j]){dp[i][j]dp[i][k]dp[k][j];}}}}// 输出从起点st到终点ed的最短距离保留两位小数printf(%.2lf,dp[st][ed]);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