Dijkstra 求助
  • 板块学术版
  • 楼主智子
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/8/13 21:03
  • 上次更新2023/11/4 10:45:56
查看原帖
Dijkstra 求助
132435
智子楼主2021/8/13 21:03

正确的 Dijkstra 到底需不需要 vis 数组啊qwq

OI Wiki 给出的模板没有 vis 数组

vector<vector<LL>> Ps;  // 图的邻接矩阵
vector<LL> dist;        // min_len 的运行结果存储位置

// i: 源点在点集中的下标
void min_len(size_t i) {
  using Pair = pair<LL, size_t>;  // pair 的排序是先第一分量后第二分量,
                                  // 通过这个可以调整它在堆中的位置

  // 初始化 dist
  for (auto &k : dist) k = LLONG_MAX;
  dist[i] = 0;

  // 初始化小根堆
  priority_queue<Pair, vector<Pair>, greater<Pair>> Q;  // 小根堆
  Q.push(Pair(0, i));

  while (!Q.empty()) {
    auto k = Q.top().second;
    Q.pop();
    for (size_t i = 0; i < Ps[k].size(); i++) {
      // 如果 k 和 i 有边连(这里设置 Ps[k][i] == 0 时无边连接)
      if (Ps[k][i] && dist[k] + Ps[k][i] < dist[i]) {
        // 松弛操作
        dist[i] = dist[k] + Ps[k][i];
        Q.push(Pair(dist[i], i));
      }
    }
  }
}

但蓝书的模板上使用了 vis 数组,感觉好奇怪……

2021/8/13 21:03
加载中...