qidao123.com技术社区-IT企服评测·应用市场

标题: Dijkstra单源最短路模板 [打印本页]

---

作者: 农妇山泉一亩田    时间: 2025-4-22 20:14
标题: Dijkstra单源最短路模板
来更新一下雷达图的凹角吧，\(Dijkstra\) 可以处置惩罚单源最短路，即跑一次可以求出指定点到每个点的最短距离。无法处置惩罚负边权。
[code]#include using namespace std;int pre[100010], k; //存图bool vis[100010];//是否访问过int n, m, s; //输入struct edge {        int to, nxt, len; //链式前项星} e[1010100];struct node {        int pos, dis; //编号，距离        bool operator < (const node &cmp) const {                return dis > cmp.dis;//重载小根堆        }} dis[1010100];priority_queue  q;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[tmp.pos]) continue; //优先剪枝掉访问过的点                vis[tmp.pos] = 1;                //开始松弛该节点                for (int i = pre[tmp.pos]; i; i = e.nxt) {                        //遍历该节点的所有相邻节点                        int to = e.to;                        if (dis[to].dis > dis[tmp.pos].dis + e.len) {                                //如果s到当前遍历到节点的距离大于经过tmp节点到达当前遍历到节点的距离，即可以进行距离的更新                                dis[to].dis = dis[tmp.pos].dis + e.len;                                q.push({to,dis[to].dis});                        }                }        }}int main() {        scanf("%d%d%d", &n, &m, &s);        for (int i = 1; i

---

欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)

Powered by Discuz! X3.4