Перелёты

@1timchik1 · Регистрация: 27.06.2020

Студворк — интернет-сервис помощи студентам

Не могу понять, почему программа не проходит по времени с асимптотикой O(n^3) при ограничении n <= 1000 и тайм лимиту в 1,5 с
При разработке нового самолёта для внутренних авиалиний Байтландии возник вопрос, какого размера делать ёмкости для топлива. Для этого для каждой пары городов была собрана информация по расходу топлива на перелёт между этими городами. При этом на перелёт из A в B и из B в A может быть затрачено разное количество топлива.

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

Формат ввода
В первой строке задано одно целое число n (1 ≤ n ≤ 1000) — число городов в Байтландии.

Каждая из последующих n строк содержит по n целых чисел. a_ij (j-ое число в i-ой строке) равно расходу топлива при перелёте из i-ого города в j-ый (0 ≤ a_ij < 10⁹, a_ii=0 для всех i).

Формат вывода
Выведите одно целое число — ответ к задаче.
Ввод
4
0 10 12 16
11 0 8 9
10 13 0 22
13 10 17 0

Вывод
10

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    vector<vector<int>> gr(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> gr[i][j];
        }
    }
    
    int ans = -1e9;
    for (int k = 0; k < n; k++) {
        ans = -1e9;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                gr[i][j] = min(gr[i][j], max(gr[i][k], gr[k][j]));
                ans = max(ans, gr[i][j]);
            }
        }
    }
    cout << ans;
}

@yMHiy yoz · 31.05.2022, 21:25

Алгоритм сам по себе не рабочий.
Чё мы делаем?
Перебираем пути из i в j и смотрим не лучше ли нам полететь через k. А если лучше полететь через k и m?

Дейкстру осваивайте. За n^2 все кратчайшие пути из вершины A.

@QueryMonkey · 31.05.2022, 21:44

yMHiy yoz, это по прежнему О(n³) для рассчёта баков, так?

@Shamil1 · 01.06.2022, 11:35

Есть множество рёбер.
Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN).

Берём из Кучи по одному и проверяем, есть ли альтернативный более короткий путь.
Если нет, то это ответ.
Если да, то берём следующее ребро.

@QueryMonkey · 01.06.2022, 16:57

Сообщение от Shamil1

Есть множество рёбер.
Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN).

Берём из Кучи по одному

Цель сортировки непонятна. Если потом все равно перебираем все по одному.

Сообщение от Shamil1

и проверяем, есть ли альтернативный более короткий путь.
Если нет, то это ответ.

Ответ к задаче? Или ответ к паре точек? У нас О(n²) пар.

Непонятно как "проверяем" на полном графе между любыми двумя точками существует О(n!) путей без циклов.

Я совсем не понял ваше решение.

@Shamil1 · 01.06.2022, 17:18

Сообщение от QueryMonkey

Цель сортировки непонятна. Если потом все равно перебираем все по одному.

Берём максимальный элемент.
https://ru.wikipedia.org/wiki/... 1%87%D0%B0

Сообщение от QueryMonkey

Ответ к задаче? Или ответ к паре точек? У нас О(n²) пар.

Ответ к задаче. Нам нужно найти максимальный перелёт.

Сообщение от QueryMonkey

Непонятно как "проверяем" на полном графе между любыми двумя точками существует О(n!) путей без циклов.

Поиск кратчайшего пути между началом и концом ребра алгоритмом Дейкстры.

Добавлено через 14 минут
з.ы. Так как мы в Кучу не докладываем, то можно использовать отсортированный список.

@QueryMonkey · 01.06.2022, 18:29

Shamil1, теперь понял, спасибо.

Добавлено через 19 минут
Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом.

Например: А->Б:2, но а-в-г-д-б по одному хотя весь путь 4.
Это значит мне нужен бак размера 1, тк разрешено заправляться в каждом городе.

Ваш алгоритм даёт 2.

Добавлено через 13 минут
1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя)

Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1).

@Shamil1 · 01.06.2022, 18:39

Сообщение от QueryMonkey

Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом.

Согласен, подвох есть.
На самом деле нас интересует любой путь, не использующий текущее ребро. Можно использовать обход в ширину.

@Shamil1 · 01.06.2022, 18:56

QueryMonkey,
Но в результате получатется тот же n³, так как у нас n² рёбер. Только появляются дополнительные условия выхода из циклов.

@QueryMonkey · 01.06.2022, 19:53

Shamil1,

Ну как же, см выше (копирую для удобства читателя):

1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя)

Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1).

Задача проще чем та, над которой трудился Дейкстра.

Добавлено через 1 минуту
Столбцы и строки относятся к матрице в первом сообщении темы.

Добавлено через 40 минут
В коде моя идея выглядит примерно так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
#define NODES   4
 
int aa[NODES][NODES] = 
{
  { 0, 10, 12, 16},
  {11,  0,  8,  9},
  {10, 13,  0, 22},
  {13, 10, 17,  0}
};
 
int main()
{
  int x = 0; // result
 
  for( int i = 0 ; i < NODES ; ++i )
  {
    unsigned r = ~0, c = ~0;
    for( int j = 0 ; j < NODES ; ++j )
      if( j != i )
      {
        if( aa[i][j] < r ) r = aa[i][j];
        if( aa[j][i] < c ) c = aa[j][i];
      }
    if( r > x ) x = r;
    if( c > x ) x = c;
  }
  printf( "%d\n", x );
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@yMHiy yoz Заблокирован
	31.05.2022, 21:25
	Алгоритм сам по себе не рабочий. Чё мы делаем? Перебираем пути из i в j и смотрим не лучше ли нам полететь через k. А если лучше полететь через k и m? Дейкстру осваивайте. За n^2 все кратчайшие пути из вершины A. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	31.05.2022, 21:44
	yMHiy yoz, это по прежнему О(n³) для рассчёта баков, так? 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,884
	01.06.2022, 11:35
	Есть множество рёбер. Сортируем их в порядке убывания веса. То есть, помещаем в Кучу (Пирамиду) за O(N logN). Берём из Кучи по одному и проверяем, есть ли альтернативный более короткий путь. Если нет, то это ответ. Если да, то берём следующее ребро. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	01.06.2022, 18:29
	Shamil1, теперь понял, спасибо. Добавлено через 19 минут Вижу подвох. Дейкстра находит кратчайший путь, но нас интересует путь с кратчайшим максимальным сегментом. Например: А->Б:2, но а-в-г-д-б по одному хотя весь путь 4. Это значит мне нужен бак размера 1, тк разрешено заправляться в каждом городе. Ваш алгоритм даёт 2. Добавлено через 13 минут 1timchik1, считаете минимум для каждой строки и для каждого столбца (исключая ноль-себя) Максимальное из этих 2N чисел - ответ к задаче. Время О(N²), память О(1). 0

@Shamil1 Модератор 3135 / 2282 / 469 Регистрация: 26.03.2015 Сообщений: 8,884
	01.06.2022, 18:56
	QueryMonkey, Но в результате получатется тот же n³, так как у нас n² рёбер. Только появляются дополнительные условия выхода из циклов. 0