当前位置：首页 > news >正文

题解：AcWing 6057 最短路

news 2026/5/1 22:13:50

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

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

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

【题目来源】

AcWing：6057. 最短路 - 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

【输出样例】

【算法标签】

#Dijkstra#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;// 长整型别名typedefpair<LL,int>PLI;// 优先队列元素类型：(距离, 顶点)constintN=100005;// 最大顶点数constintM=1000005;// 最大边数（无向图，双倍边）// 链式前向星存储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(){intx=0,f=1;// x: 结果, f: 符号charc=getchar();while(c<'0'||c>'9'){// 跳过非数字字符if(c=='-')f=-1;// 负号c=getchar();}while(c>='0'&&c<='9'){// 读取数字x=x*10+c-'0';c=getchar();}returnx*f;// 返回结果×符号}// Dijkstra算法voiddijkstra(ints){memset(dis,0x3f,sizeof(dis));// 初始化距离为无穷大dis[s]=0;// 起点距离为0// 小顶堆优先队列，(距离, 顶点)priority_queue<PLI,vector<PLI>,greater<PLI>>pq;pq.push({0,s});// 起点入队while(!pq.empty()){auto[d,u]=pq.top();// 取出当前距离最小的顶点pq.pop();if(vis[u])continue;// 如果已确定，跳过vis[u]=true;// 标记为已确定// 遍历顶点u的所有邻接边for(inti=head[u];i;i=nxt[i]){intv=to[i];// 邻接顶点if(!vis[v]&&dis[v]>dis[u]+w[i]){// 松弛操作dis[v]=dis[u]+w[i];// 更新距离pq.push({dis[v],v});// 入队}}}}intmain(){n=read();// 读入顶点数m=read();// 读入边数// 读入所有边for(inti=0;i<m;i++){inta=read(),b=read(),c=read();// 边的两端点和权重if(a==b)continue;// 跳过自环add(a,b,c);// 无向图，添加双向边add(b,a,c);}dijkstra(1);// 从顶点1开始Dijkstra算法printf("%lld\n",dis[n]);// 输出从1到n的最短距离return0;// 程序正常结束}