Четыре службы связаны между собой односторонними каналами связи, по которым ежедневно передаётся важная информация. Ниже в таблице представлено приблизительное время, за которое…
Четыре службы связаны между собой односторонними каналами связи, по которым ежедневно передаётся важная информация. Ниже в таблице представлено приблизительное время, за которое передается важная информация между службами если отправить письма в Понедельник, Среду, Четверг и Пятницу - таблица слева и в остальные дни – таблица справа. Числа в ячейках означают количество дней, которое требуется для доставки сообщения, например, если в Субботу отправить сообщение из пункта А в пункт Б, то оно придет в Понедельник, -1 означает что соединение не установлено. За какое минимальное время будет доставлено письмо, отправленное из службы А в службу Г, если сообщение было отправлено во вторник? Например, если отправить в понедельник сообщение из А в Б, то сообщение придет во вторник. По строкам находится район отправления, а в столбцах район - получатель.
Спасибо. Чтобы дать точный ответ и пошаговое решение, мне нужны сами две таблицы с временными данными. Сейчас в сообщении не приведены значения из таблиц (левая — для понедельника, среды, четверга и пятницы; правая — для остальных дней: вторник, суббота, воскресенье). Без этих чисел невозможно вычислить минимальное время А → Г, отправленное во вторник.
Что мне нужно прислать:
- Таблица слева: матрица 4x4 (рядами отправитель A, B, В, Г; столбцами получатель A, B, В, Г) для дней понедельник, среда, четверг и пятница. В каждой клетке either число дней доставки или -1 (если канал не установлен) для соответствующего дня.
- Таблица справа: такая же матрица 4x4 для остальных дней недели (вторник, суббота, воскресенье).
- Уточнение: дни недели в таблицах соответствуют тем же обозначениям, что и примеры (A, B, В, Г). Если хочется, могу использовать ваши обозначения: A, B, V, G (или А, Б, В, Г по-русски).
Как я буду решать после получения данных:
- Обозначим дни недели численно: Mon=0, Tue=1, Wed=2, Thu=3, Fri=4, Sat=5, Sun=6.
- Правила выбора таблицы:
- Если в момент отправления день недели равен Mon, Wed, Thu или Fri — используем левую таблицу.
- Если день равен Tue, Sat или Sun — используем правую таблицу.
- Построю временной расширенный граф:
- Состояния: (служба u, день недели d), где u ∈ {A, B, V, G}, d ∈ {0..6}.
- Ребра: из (u, d) в (v, (d + t) mod 7) с весом t, если в соответствующей таблице для дня d есть значение t ≥ 1 для перехода u → v; если значение -1, такого ребра нет.
- Т.е. длительность t зависит от дня отправления d и от пары отправитель-получатель.
- Запущу алгоритм кратчайшего пути Дейкстры из начального состояния (A, Tue) = (A, 1). Ответом будет минимальная сумма длительностей по всем путям, ведущим в любое состояние (Г, d) (то есть в любую «сцену» дня прибытия). Эта сумма и есть искомое минимальное число дней.
- При необходимости могу также выписать сам путь (последовательность переходов) и даты прибытия на каждом шаге.
Если хотите, могу привести пример на выдуманных числах, чтобы показать, как считать вручную, но это будет не ваш конкретный ответ. Чтобы идти дальше точно, пришлите две таблицы (изображение или текст). Я сразу посчитаю минимальное время А → Г при отправке во вторник и распишу все шаги по дням и по ребрам графа.
