Dijkstra单源最短路模板
来更新一下雷达图的凹角吧，\(Dijkstra\) 可以处理单源最短路，即跑一次可以求出指定点到每个点的最短距离。无法处理负边权。#include using namespace std;int pre, k; //存图bool vis;//是否访问过int n, m, s; //输入struct edge { int to, nxt, len; //链式前项星} e;struct node { int pos, dis; //编号，距离 bool operator < (const node &cmp) const { return dis > cmp.dis;//重载小根堆 }} dis;priority_queueq;void add(int u, int v, int l) { e[++k] = {v, pre, l}; pre = k;}void dijkstra() { dis.dis = 0;//别忘了 q.push({s, 0}); //起点入队 while (!q.empty()) { node tmp = q.top();//优先选择距离最小的点 q.pop();//别忘了这个要不然就逝了，要一开始就pop，不然有可能pop掉刚刚push的数 if (vis) continue; //优先剪枝掉访问过的点 vis = 1; //开始松弛该节点 for (int i = pre; i; i = e.nxt) { //遍历该节点的所有相邻节点 int to = e.to; if (dis.dis > dis.dis + e.len) { //如果s到当前遍历到节点的距离大于经过tmp节点到达当前遍历到节点的距离，即可以进行距离的更新 dis.dis = dis.dis + e.len; q.push({to,dis.dis}); } } }}int main() { scanf("%d%d%d", &n, &m, &s); for (int i = 1; i
页:
[1]