是否有可能以某种方式加速 Dijkstra 算法的实现？

我对“graph”类的实现，PathWeights方法实现了 Dijkstra 的有向加权图算法：

const int HUGE_NUMBER = 100000000; //

typedef std::pair<int, uint64_t> Arrow;

bool ArrowCmp(const Arrow &lhs, const Arrow &rhs) {
  return lhs.first < rhs.first;
}

class Graph {
  int size_;

  std::vector<std::vector<Arrow>> arrows;
  std::vector<int> parents;

 public:
  explicit Graph(int size) {
    size_ = size;
    arrows.resize(size);
    parents.resize(size);
  }

  void AddEdge(int from, int to, uint64_t cost) {
    if (from == to) {
      return;
    }

    auto arrow = std::make_pair(to, cost);

    auto pos = std::lower_bound(arrows[from].begin(),
                                arrows[from].end(),
                                arrow,
                                ArrowCmp);

    if (pos == arrows[from].end()) {
      arrows[from].push_back(arrow);
    } else if (pos->first != arrow.first) {
      arrows[from].insert(pos, arrow);
    } else {
      (*pos).second = std::min(cost, pos->second);
    }
  }

  std::vector<int> Path(int from, int to) {
    PathWeights(from);

    std::vector<int> ret;

    for (int cv = to; cv != from; cv = parents[cv]) {
      ret.push_back(cv);
    }

    ret.push_back(from);
    std::reverse(ret.begin(), ret.end());

    return ret;
  }

  std::vector<uint64_t> PathWeights(int start) {
    std::vector<uint64_t> lens(size_);

    std::fill(lens.begin(), lens.end(), HUGE_NUMBER);
    lens[start] = 0;

    int count = 0;

    std::set<std::pair<uint64_t, int>> sorted_ps;

    sorted_ps.insert(std::make_pair(0, start));

    while (!sorted_ps.empty()) {
      int from = sorted_ps.begin()->second;
      sorted_ps.erase(sorted_ps.begin());

      for (int to = 0; to < size_; ++to) {
        auto arrow = std::make_pair(to, 0ul);
        auto pos = std::lower_bound(arrows[from].begin(),
                                    arrows[from].end(),
                                    arrow,
                                    ArrowCmp);

        if (pos == arrows[from].end()) {
          continue;
        }

        if (pos->first != to) {
          continue;
        }

        auto cost = pos->second;

        if (lens[from] + cost < lens[to]) {
          sorted_ps.erase(std::make_pair(lens[to], to));
          lens[to] = lens[from] + cost;
          parents[from] = to;
          sorted_ps.insert(std::make_pair(lens[to], to));
        }
      }
      ++count;
    }

    return lens;
  }
};

我正在尝试从封闭式比赛中解决问题，问题的条件可以表述如下：

1. 给定一个可以有环和多条边的有向加权图
2. 权重是从零到二的整数
3. 顶点少于 5000，边少于 20000
4. 找到两个给定顶点之间最简单路径的权重
5. Main对 PathWeights 的调用不超过 10000次
6. 程序应使用不超过 64Mb 的内存，运行不超过 3 秒

现在程序可以正常工作，但速度很慢。

第一个解决方案将边存储为邻接矩阵，并使用布尔数组通过线性搜索来搜索合适的顶点。现在我正在使用传出边的向量，按升序结束顶点索引排序，并设置为选择适当的顶点。有没有其他方法可以加快这个解决方案？在这些条件下是否值得使用另一种算法？