Dijkstra算法（模板）pta

Dijkstra算法模板代码
对于Dijkstra算法，在处理最短路径问题时，该算法提供了一种有效的方法来计算单源最短路径。下面是一个基于优先队列优化版本的C++实现示例[^2]：
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e5 + 7, INF = 0x3f3f3f3f;
int n, m, s; // 节点数量n，边的数量m，起点s
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII>> heap;
vector<pair<int,int>> adj[N]; // 邻接表存储图结构
bool st[N];
int dist[N];

void dijkstra(int start){
memset(dist,INF,sizeof dist);
dist[start]=0;

while(!heap.empty()){
auto t=heap.top();
heap.pop();

int ver=t.second,distance=t.first;

if(st[ver]) continue;
st[ver]=true;

for(auto item : adj[ver]){
int v=item.first,w=item.second;

if(dist[v]>distance+w){
dist[v]=distance+w;
heap.push({dist[v],v});
}
}
}
}
登录后复制
此段代码实现了带权重有向图中的单源最短路径查询功能。其中adj[]用于保存每条边及其对应的权重；st[]标记节点是否已被访问过；而dist[]则记录从起始位置到达各个顶点所需的最小距离。
当面对无向图的情况时，只需在构建邻接表的过程中对双向连接做相应调整即可[^1]。