Моя реализация класса "граф", метод PathWeights реализует алгоритм Дейкстры для ориентированного взвешенного графа:
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 не больше 10000 вызовов PathWeights
- Программа должна использовать не больше 64Mb памяти, работать не дольше 3 секунд
Сейчас программа работает верно, но медленно.
Первое решение хранило ребра в виде матрицы смежности, а подходящую вершину искало линейным поиском, использую булевый массив. Сейчас я использую вектор исходящих ребер, отсортированныц по возрастанию индекса конечной вершины, и set для выбора подходящей вершины. Можно ли как-то еще ускорить это решение? Стоит ли при этих условиях использовать другой алгоримт?
Вершин меньше 5000, ребер меньше 20000
- значит, графы с большим количество вершин разреженные, для таких есть специальные методы с лучшей асимптотикой