Телепорты и турболифты
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Словари и множества
На космическом корабле n комнат с номерами от 1 до n; colors[i] — цвет комнаты i + 1 (строка из одного-двух символов a-z, 0-9). Из любой комнаты можно мгновенно, за 0 секунд, телепортироваться в любую другую комнату того же цвета.
Кроме того, есть односторонние турболифты: lifts[j] = [a, b, t] увозит из комнаты a в комнату b за t секунд (0 ≤ t ≤ 1000); лифтов может быть несколько, в том числе из комнаты в неё же. Для каждого запроса queries[j] = [p, q] найдите наименьшее время пути из комнаты p в комнату q, а если пути нет, ответьте -1. Верните список ответов в порядке запросов.
Пример: ["gl", "t3", "t3"], [[1, 2, 217], [3, 2, 567], [1, 1, 21]], [[2, 1], [2, 3]] → [-1, 0].
Источник: Coding Competitions Archive, kickstart/2013/round_a/spaceship_defence · © Google LLC · Apache-2.0 · условие переведено и дополнено