我对“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;
}
};
我正在尝试从封闭式比赛中解决问题，问题的条件可以表述如下：
- 给定一个可以有环和多条边的有向加权图
- 权重是从零到二的整数
- 顶点少于 5000，边少于 20000
- 找到两个给定顶点之间最简单路径的权重
- Main对 PathWeights 的调用不超过 10000次
- 程序应使用不超过 64Mb 的内存，运行不超过 3 秒
现在程序可以正常工作，但速度很慢。
第一个解决方案将边存储为邻接矩阵，并使用布尔数组通过线性搜索来搜索合适的顶点。现在我正在使用传出边的向量，按升序结束顶点索引排序，并设置为选择适当的顶点。有没有其他方法可以加快这个解决方案？在这些条件下是否值得使用另一种算法？
