Расчет расстояний между узлами в графе с отрицательными циклами (двойное переполнение)

Полное раскрытие: это для онлайн-курса.

Код вычисляет расстояния между начальным узлом на графике и всеми другими узлами, используя алгоритм Беллмана-Форда. График может содержать отрицательные циклы: в этом случае выходные данные должны представлять это расстояние с помощью «-». Если между начальным узлом и другим узлом нет связи, он должен указывать ‘*’. Иначе, это должно вывести расстояние.

Код работает, но я считаю, что есть проблема переполнения, которую я не знаю, как решить. Ограничения определяют следующие максимальные значения:

• Узлы: 10 ^ 3;
• Края: 10 ^ 4;
• Вес ребра: 10 ^ 9

Тестирование для всех связанных с логикой угловых случаев не привело к проблемам, все работало правильно. Тест, который не пройден, (скорее всего) связан с переполнением.

Код

void bfs(vector<vector<int> > &adj, queue<int> q, vector<bool> &shortest) {
int size = adj.size();
vector<bool> visited(size, false);
while (!q.empty()) {
int v = q.front();
if (visited[v]) {
q.pop();
} else {
q.pop();
for (int i = 0; i < adj[v].size(); i++) {
shortest[adj[v][i]] = true;
q.push(adj[v][i]);
}
}
visited[v] = true;
}
}

void shortest_paths(vector<vector<int> > &adj, vector<vector<int> > &cost, int s,
vector<double> &distance, vector<bool> &reachable, vector<bool> &shortest) {
int size = adj.size();
distance[s] = 0;
reachable[s] = true;
queue<int> negative_cycle;
// Set initial distances and get negative cycles
for (int i = 0; i <= size; i++) {
for (int j = 0; j < size; j++) {
for (int k = 0; k < adj[j].size(); k++) {
// Edge relaxation
if (distance[adj[j][k]] > distance[j] + cost[j][k]) {
reachable[adj[j][k]] = true;
if (i == size) {
// Store negative cycles
negative_cycle.push(adj[j][k]);
shortest[adj[j][k]] = true;
}
distance[adj[j][k]] = distance[j] + cost[j][k];
}
}
}
}
bfs(adj, negative_cycle, shortest);
}

и основной

int main() {
int n, m, s;
std::cin >> n >> m;
vector<vector<int> > adj(n, vector<int>());
vector<vector<int> > cost(n, vector<int>());
for (int i = 0; i < m; i++) {
double x, y, w;
std::cin >> x >> y >> w;
adj[x - 1].push_back(y - 1);
cost[x - 1].push_back(w);
}
std::cin >> s;
s--;
vector<double> distance(n, std::numeric_limits<double>::infinity());
vector<bool> reachable(n, false);
vector<bool> shortest(n, false);
shortest_paths(adj, cost, s, distance, reachable, shortest);
for (int i = 0; i < n; i++) {
if (!reachable[i]) {
std::cout << "*\n";
} else if (shortest[i]) {
std::cout << "-\n";
} else {
std::cout << distance[i] << "\n";
}
}
}

Я использую double и бесконечность, так как это необходимо для алгоритма (вы можете прочитать об этом Вот). Из гугля, который я сделал, я понял, что это не должно быть переполнено, поскольку максимально возможное расстояние будет 10 ^ 4 * 10 ^ 9 = 10 ^ 13, которое все еще находится в пределах диапазона double. У меня нет большого опыта использования бесконечности или подобных двойников, и из того, что я исследовал, я не мог проследить проблему.

Есть ли альтернатива использованию двойной бесконечности (так как long longего нет и его max_size нельзя использовать в контексте проблемы)? Может ли быть в этом случае двойное переполнение или другие связанные с этим проблемы (ошибки сравнения и т. Д.)?