本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6057. 最短路 - AcWing题库【题目描述】给定M MM条边N NN个点的带权无向图。点的编号从1 11到N NN。求1 11到N NN的最短路。【输入】第一行包含两个整数N , M N,MN,M。接下来M MM行每行包含三个整数a i , b i , c i a_i,b_i,c_iai​,bi​,ci​表示点a i , b i a_i,b_iai​,bi​之间有一条长度为c i c_ici​的路。【输出】一个整数表示从1 11到N NN的最短距离。【输入样例】4 4 1 2 1 2 3 1 3 4 1 2 4 1【输出样例】2【算法标签】#Dijkstra#【代码详解】#includebits/stdc.husingnamespacestd;typedeflonglongLL;// 长整型别名typedefpairLL,intPLI;// 优先队列元素类型(距离, 顶点)constintN100005;// 最大顶点数constintM1000005;// 最大边数无向图双倍边// 链式前向星存储inthead[N];// head[i]: 顶点i的第一条边的编号intto[M];// to[i]: 第i条边的终点intw[M];// w[i]: 第i条边的权重intnxt[M];// nxt[i]: 下一条边的编号inttot;// 当前边的编号LL dis[N];// 存储从起点到各顶点的最短距离boolvis[N];// 标记顶点是否已确定最短距离intn,m;// 顶点数边数// 添加有向边inlinevoidadd(intu,intv,intval){to[tot]v;// 新边的终点w[tot]val;// 新边的权重nxt[tot]head[u];// 新边指向原来的第一条边head[u]tot;// 更新顶点u的第一条边为新边}// 快速读入函数inlineintread(){intx0,f1;// x: 结果, f: 符号charcgetchar();while(c0||c9){// 跳过非数字字符if(c-)f-1;// 负号cgetchar();}while(c0c9){// 读取数字xx*10c-0;cgetchar();}returnx*f;// 返回结果×符号}// Dijkstra算法voiddijkstra(ints){memset(dis,0x3f,sizeof(dis));// 初始化距离为无穷大dis[s]0;// 起点距离为0// 小顶堆优先队列(距离, 顶点)priority_queuePLI,vectorPLI,greaterPLIpq;pq.push({0,s});// 起点入队while(!pq.empty()){auto[d,u]pq.top();// 取出当前距离最小的顶点pq.pop();if(vis[u])continue;// 如果已确定跳过vis[u]true;// 标记为已确定// 遍历顶点u的所有邻接边for(intihead[u];i;inxt[i]){intvto[i];// 邻接顶点if(!vis[v]dis[v]dis[u]w[i]){// 松弛操作dis[v]dis[u]w[i];// 更新距离pq.push({dis[v],v});// 入队}}}}intmain(){nread();// 读入顶点数mread();// 读入边数// 读入所有边for(inti0;im;i){intaread(),bread(),cread();// 边的两端点和权重if(ab)continue;// 跳过自环add(a,b,c);// 无向图添加双向边add(b,a,c);}dijkstra(1);// 从顶点1开始Dijkstra算法printf(%lld\n,dis[n]);// 输出从1到n的最短距离return0;// 程序正常结束}【运行结果】4 4 1 2 1 2 3 1 3 4 1 2 4 1 2