Задача
В $2163$ году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:
- Червячные дыры являются односторонними.
- Время путешествия по любому тоннелю равно нулю.
- Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
- Звездная система в своих границах может иметь несколько концов червячных дыр.
- По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
- Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
- Оба конца червячной дыры не могут находиться в одной звездной системе.
- Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на $15$ лет в будущее, а другая на $42$ года в прошлое.
- Возьмем первое ребро из массива $canals$, и проведем сравнение: если исходная длина пути конца данного ребра из исходного массива $distance$ больше, чем сумма длины пути начала массива и стоимости прохода по данному ребру $canals[].t$, то изменим в массиве $distance$ элемент с номером конца исходного ребра, и изменим индикатор изменений $subs$, чтобы показать, что в ходе данного прохода были внесены изменения.
- Переходим к следующему ребру.
Известный физик, живущий на Земле, хочет использовать червячные дыры для исследования теории Большого Взрыва. Поскольку двигатель искривления пространства еще не изобретен, невозможно напрямую путешествовать между звездными системами. Однако это можно делать при помощи червячных дыр.
Ученый хочет достигнуть цикла червячных дыр, который поможет ему попасть в прошлое. Двигаясь по этому циклу несколько раз, можно прийти ко времени, когда имел место Большой Взрыв и наблюдать его собственными глазами. Напишите программу, которая определяет существование такого цикла.
Входные данные
Первая строка содержит количество звездных систем $n$ $(1 ≤ n ≤ 1000)$ и количество червячных дыр $m$ $(0 ≤ m ≤ 2000)$. Звездные системы пронумерованы от $0$ (наша солнечная система) до $n — 1$. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа $x$, $y$ и $t$. Эти числа указывают на возможность передвижения из звездной системы с номером $x$ в звездную систему с номером $y$, при этом время изменяется на $t$ $(-1000 ≤ t ≤ 1000)$ лет.
Выходные данные
Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible».
Тесты
| Входные данные | Выходные данные |
| $3$ $3$ $0$ $1$ $1000$ $1$ $2$ $15$ $2$ $1$ $-42$ |
possible |
| $4$ $4$ $0$ $1$ $10$ $1$ $2$ $20$ $2$ $3$ $30$ $3$ $0$ $-60$ |
not possible |
| $3$ $3$ $0$ $1$ $-100$ $1$ $2$ $1$ $2$ $1$ $0$ |
not possible |
|
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; import java.lang.*; import java.io.*; class Main { private static class Node { private int x; private int y; private int t; private Node(int x, int y, int t) { this.x = x; this.y = y; this.t = t; } } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); Node r = null; Node[] canals = new Node[m + 1]; for (int i = 0; i < m; i++) { int x = in.nextInt(); int y = in.nextInt(); int t = in.nextInt(); r = new Node(x, y, t); canals[i] = r; } int INF = 2000000; int[] distance = new int[n + 1]; int subs = -1; for (int i = 0; i < n; i++) { subs = -1; for (int j = 0; j distance[canals[j].x] + canals[j].t) { distance[canals[j].y] = Math.max (-INF, distance[canals[j].x] + canals[j].t); subs = canals[j].y; } } } if (subs == -1) { System.out.println("not possible"); } else { System.out.println("possible"); } } } |
Описание решения
Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана.
Создадим массив на $n$ элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью $n$ элементов нет отрицательных циклов, то после $n-1$ прохождения изменения в массиве кратчайших расстояний не будет. Поэтому, будем выполнять следующее $n$ раз:
Если после во время последнего прохода ни разу не была изменена переменная $subs$, то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».