Advertisement
Dmaxiya

迪杰斯特拉 参考代码

Mar 17th, 2025
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. typedef long long LL;
  2. const int maxn = 100000 + 100;
  3. struct Node {
  4.     int pos;
  5.     LL dis;
  6.     // 无参与有参构造函数
  7.     Node() {}
  8.     Node(int pos, LL dis) : pos(pos), dis(dis) {}
  9. };
  10.  
  11. // 重载 Node 的小于运算符
  12. // 由于 priority_queue 默认为大顶堆,这里将 dis 的比较取反,可以得到关于 Node 的小顶堆
  13. bool operator<(const Node &a, const Node &b) {
  14.     return a.dis > b.dis;
  15. }
  16.  
  17. bool vis[maxn];             // 标记节点是否已确认最短路径,非常重要,没有这个判断可能 TLE
  18. LL dis[maxn];               // 记录最短距离
  19. vector<Node> G[maxn];       // 图的邻接表结构
  20. priority_queue<Node> que;   // 用于快速得到距离最短的节点的优先队列
  21.  
  22. void dij(int s) {
  23.     // 将所有节点的距离初始化为“无穷大”
  24.     // 该“无穷大”值可以与其它较小值相加且不发生溢出
  25.     memset(dis, 0x3f, sizeof(dis));
  26.     // 初始化起点距离为 0
  27.     que.push(Node(s, 0));
  28.     dis[s] = 0;
  29.  
  30.     while (!que.empty()) {
  31.         // 从优先队列中取出距离最短的点
  32.         Node tmp = que.top();
  33.         que.pop();
  34.         // 如果已取出过,直接 continue,不要再重复处理,不然会被极端数据卡 TLE
  35.         if (vis[tmp.pos]) {
  36.             continue;
  37.         }
  38.         vis[tmp.pos] = true;
  39.  
  40.         for (Node &node : G[tmp.pos]) {
  41.             if (dis[node.pos] > tmp.dis + node.dis) {
  42.                 // 能通过 tmp.pos 走到 node.pos,且距离更短,就更新距离,且入堆
  43.                 dis[node.pos] = tmp.dis + node.dis;
  44.                 que.push(Node(node.pos, dis[node.pos]));
  45.             }
  46.         }
  47.     }
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement