题解：AcWing 6055 最短路径

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

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

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

【题目来源】

AcWing：6055. 最短路径 - 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 nn（n nn为图G GG的顶点数）。

【输入】

第1 11行：一个正数n nn，表示图G GG的顶点总数。

第2 22行：一个整数，表示源点v 0 v_0v0​（v 0 ∈ V v_0\in Vv0​∈V，v 0 v_0v0​可以是图G GG中任意一个顶点）。

第3 33至第n + 2 n+2n+2行，用一个邻接矩阵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#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineN105#defineINF0x3f3f3f3fintn,v0;// n: 顶点数, v0: 源点intedge[N][N];// 邻接矩阵存储图intdis[N];// 从源点到各顶点的最短距离boolvis[N];// 顶点是否在队列中的标记// SPFA算法（Shortest Path Faster Algorithm）voidspfa(){queue<int>que;// 队列用于存储待处理的顶点que.push(v0);// 源点入队vis[v0]=true;// 标记源点在队列中memset(dis,0x3f,sizeof(dis));// 初始化所有距离为无穷大dis[v0]=0;// 源点到自身的距离为0while(que.empty()==false)// 当队列不为空{intu=que.front();// 取出队首顶点que.pop();vis[u]=false;// 标记顶点不在队列中// 遍历顶点u的所有邻接点for(inti=1;i<=n;++i){// 如果存在从u到i的边，且可以松弛if(edge[u][i]<INF&&dis[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(inti=1;i<=n;++i){for(intj=1;j<=n;++j){if(scanf("%d",&a)==1)// 如果是正确输入，会返回1{edge[i][j]=a;// 存储边权}else{edge[i][j]=INF;// 如果没有边，设置为无穷大}}}spfa();// 执行SPFA算法// 输出从源点到其他各顶点的最短距离for(inti=1;i<=n;++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