A29825.Dijkstra 优先队列
2026-01-10 12:12:37
发布于：四川
4阅读
0回复
0点赞
//模板题：A29825.【最短路径】城市路(Dijkstra) {jsdhwdmaX}详见ACGO
//法一：迪杰斯特拉_dijkstra
//朴素版的写法
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;//定义最大城市数
const int INF=0x3f3f3f3f;//定义无穷大
int n,m;//n个城市，m条路
int g[N][N];//定义邻接矩阵g[i][j]代表i到j的距离
int dist[N];//从起点到i的最短路
bool st[N];//标记城市i的最短路距离是否确定
//定义迪杰斯特拉的函数
int dijkstra(){
//初始化数组
memset(dist,0x3f,sizeof(dist));
dist[1]=0;//标记起点到自己的距离为0
//循环n次，每次确定一个城市的最短路
for(int i=0;i<n;i++){
int t=-1;//用来存储找到最小距离城市的编号
for(int j=1;j<=n;j++){
//如果城市j未确定最短路，并且t==-1还没找到
if(!st[j]&&(t==-1||dist[j]<dist[t])){
t=j;
}
}
if(t==-1||dist[t]==INF) break;
st[t]=true;
//用城市t更新其他城市的距离
for(int j=1;j<=n;j++){
if(dist[t]+g[t][j]<dist[j]){
dist[j]=dist[t]+g[t][j];//更新距离
}
}
}
if(dist[n]==INF) return -1;
return dist[n];
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof(g));
for(int i=1;i<=n;i++){
g[i][i]=0;
}
for(int i=1;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
g[u][v]=min(g[u][v],w);
g[v][u]=min(g[v][u],w);//如果是有向图，注释掉
}
cout<<dijkstra()<<endl;
return 0;
}
//法二：优先队列(运用堆优化dijkstra)
#include <iostream> // 引入输入输出流库
#include <cstring> // 引入字符串处理库
#include <vector> // 引入动态数组库
#include <queue> // 引入优先队列库
using namespace std; // 使用标准命名空间
const int N = 20001; // 定义最大点数
const int INF = 0x3f3f3f3f; // 定义无穷大值
int n, m; // n:点数，m:边数
int dist[N]; // dist[i]表示从起点到点i的最短距离
bool st[N]; // st[i]标记点i的最短距离是否已确定
// 定义边的结构，使用邻接表存储
vector<pair<int,int>> g[N]; // g[u]存储u的所有出边，pair<v, w>
int dijkstra() {
// 初始化距离数组
memset(dist, 0x3f, sizeof(dist)); // 所有距离设为无穷大
dist[1] = 0; // 起点到自己的距离为0
// 定义优先队列（小根堆），存储pair<距离, 点编号>
priority_queue<pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>> heap;
heap.push({0, 1}); // 将起点加入优先队列，距离为0
// 当优先队列不为空时循环
while (!heap.empty()) {
// 取出堆顶元素（当前距离最小的点）
auto t = heap.top(); // 获取堆顶元素
/*
tip_auto:
auto可理解为容器里的一个接口，用于遍历
C++11新标准引入了auto类型说明符，
用它可以让编译器替我们去分析表达式所属的类型，
由于auto会让编译器根据初始值来推演变量的类型，所以auto定义的变量必须有初始值。
auto也能在一个语句中声明多个变量，一条语句只能有一个基本数据类型，
所以该语句中所有变量的初始数据类型必须一致。
eg:
int main(){
int i = 0, * p = &i; // 正确示范
auto sz = 0, pi = 3.14; // 错误示范，sz为整型，pi为double类型
return 0;
}
当然 aoto也不是万能的，
auto不能推导的场景:
1.auto不能作为函数的参数：
void TestAuto(auto a){
}
2.auto不能直接用来声明数组：
void TestAuto(){
int a[] = { 1,2,3 };
auto b[] = { 4,5,6 }; // auto类型不能出现在顶级数组类型中
}
推断规则小结：
1.对于一般类型（无const无引用），直接根据表达式的类型进行推断。
2.对于含有const的类型，会忽略顶层const属性（一般赋值时），而保留底层const属性（如指针和引用，因为涉及到了修改原对象）。
3.对于被忽略掉的引用类型或const属性，如果想要保留，需要自己额外加上&或const。
*/
heap.pop(); // 弹出堆顶元素
int ver = t.second; // 获取点编号
int distance = t.first; // 获取当前距离
// 如果这个点已经确定最短距离，跳过
if (st[ver]) continue;
// 标记这个点的最短距离已确定
st[ver] = true;
// 遍历这个点的所有邻居
for (int i = 0; i < g[ver].size(); i++) {
int j = g[ver][i].first; // 获取邻居点编号 优先队列中的first可用于访问邻居的编号
int w = g[ver][i].second; // 获取边权 优先队列中的second可用于访问自己到下一个点的边权
// 如果通过当前点到邻居点的距离更短
if (distance + w < dist[j]) {
dist[j] = distance + w; // 更新距离
heap.push({dist[j], j}); // 将邻居点加入优先队列
}
}
}
// 返回结果
if (dist[n] == INF) return -1; // 如果终点不可达，返回-1
return dist[n]; // 否则返回最短距离
}
int main() {
// 读入点数和边数
cin >> n >> m;
// 读入边信息，构建邻接表
for (int i = 0; i < m; i++) {
int u, v, w; // u:起点，v:终点，w:边权
cin >> u >> v >> w;
g[u].push_back({v, w}); // 添加有向边
// 如果是无向图，需要添加反向边：
g[v].push_back({u, w});
}
// 调用Dijkstra算法并输出结果
cout << dijkstra() << endl;
return 0;
}
这里空空如也
有帮助，赞一个