为什么 Dijkstra + priority_queue 与 Dijkstra + queue 相比表现最差？

Question

我使用带有普通队列而不是优先队列的 Dijkstra 解决了这个 problem，因为有趣的是，当我使用优先队列时，我得到了一个 TLE。我的理解是带有优先级队列的 Dijkstra 应该表现更好。我试着分析为什么会这样？我想出一个想法是这样的，因为这个问题使用的测试用例具有从 1 到 n 的边按权重递增顺序排列的图，因此维护优先级队列和 TLE 是浪费时间。我想知道情况是否确实如此，我没有遗漏任何东西。这是我对问题的解决方案：

#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
queue<pair<long, int>> pi;
vector<long> dist;
map<int, vector<pair<int, long>>> mp;

int main() {
  int m = 0, n  = 0;
  cin >> m >> n;
  while (n--) {
    int l = 0, k = 0, j = 0;
    cin >> l >> k >> j;
    mp[l].push_back(make_pair(k, j));
    mp[k].push_back(make_pair(l, j));  // for undirected edge
  }
  dist.assign(m + 1, INF);
  dist[1] = 0;
  pi.push(make_pair(0, 1));
  while (!pi.empty()) {
    pair<int, int> p = pi.front(); pi.pop();
    int u = p.second; long w = p.first;
    if (w > dist[u]) continue;
    for (auto e : mp[u]) {
      if (max(dist[u], e.second) < dist[e.first]) {
        dist[e.first] = max(dist[u], e.second);
        if (e.first != m)
          pi.push(make_pair(dist[e.first], e.first));
      }
    }
  }
  if (dist[m] == INF) cout << "NO PATH EXISTS" << endl;
  else cout << dist[m] << endl;
  return 0;
}

Answer 1

您是否更改了优先级队列的默认比较器？如果没有，那当然会慢

How can I create Min stl priority_queue?

为什么 Dijkstra + priority_queue 与 Dijkstra + queue 相比表现最差？

Why Dijkstra + priority_queue performs worst compared to Dijkstra + queue?

algorithm

queue

graph

dijkstra

priority-queue