本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing6055. 最短路径 - AcWing题库【题目描述】给出一个有向图G ( V , E ) G(V,E)G(V,E)和一个源点v 0 ∈ V v_0\in Vv0​∈V请写一个程序输出v 0 v_0v0​和图G GG中其它顶点的最短路径。只要所有的有向环权值和都是正的我们就允许图的边有负值。顶点的标号从1 11到n nnn nn为图G GG的顶点数。【输入】第1 11行一个正数n nn表示图G GG的顶点总数。第2 22行一个整数表示源点v 0 v_0v0​v 0 ∈ V v_0\in Vv0​∈Vv 0 v_0v0​可以是图G GG中任意一个顶点。第3 33至第n 2 n2n2行用一个邻接矩阵W WW给出了这个图。【输出】共包含n − 1 n-1n−1行按照顶点编号从小到大的顺序每行输出源点v 0 v_0v0​到一个顶点的最短距离。每行的具体格式参照样例。【输入样例】5 1 0 2 - - 10 - 0 3 - 7 - - 0 4 - - - - 0 5 - - 6 - 0【输出样例】(1 - 2) 2 (1 - 3) 5 (1 - 4) 9 (1 - 5) 9【算法标签】#SPFA#【代码详解】#includebits/stdc.husingnamespacestd;#defineN105#defineINF0x3f3f3f3fintn,v0;// n: 顶点数, v0: 源点intedge[N][N];// 邻接矩阵存储图intdis[N];// 从源点到各顶点的最短距离boolvis[N];// 顶点是否在队列中的标记// SPFA算法Shortest Path Faster Algorithmvoidspfa(){queueintque;// 队列用于存储待处理的顶点que.push(v0);// 源点入队vis[v0]true;// 标记源点在队列中memset(dis,0x3f,sizeof(dis));// 初始化所有距离为无穷大dis[v0]0;// 源点到自身的距离为0while(que.empty()false)// 当队列不为空{intuque.front();// 取出队首顶点que.pop();vis[u]false;// 标记顶点不在队列中// 遍历顶点u的所有邻接点for(inti1;in;i){// 如果存在从u到i的边且可以松弛if(edge[u][i]INFdis[i]dis[u]edge[u][i]){dis[i]dis[u]edge[u][i];// 松弛操作if(vis[i]false)// 如果顶点i不在队列中{vis[i]true;// 标记在队列中que.push(i);// 入队}}}}}intmain(){inta;// 临时变量用于输入scanf(%d %d,n,v0);// 输入顶点数和源点// 输入邻接矩阵for(inti1;in;i){for(intj1;jn;j){if(scanf(%d,a)1)// 如果是正确输入会返回1{edge[i][j]a;// 存储边权}else{edge[i][j]INF;// 如果没有边设置为无穷大}}}spfa();// 执行SPFA算法// 输出从源点到其他各顶点的最短距离for(inti1;in;i){if(i!v0)// 不输出源点到自身的距离{printf((%d - %d) %d\n,v0,i,dis[i]);}}return0;// 程序正常结束}【运行结果】5 1 0 2 - - 10 - 0 3 - 7 - - 0 4 - - - - 0 5 - - 6 - 0 (1 - 2) 2 (1 - 3) 5 (1 - 4) 9 (1 - 5) 9