- Описание
- Отправленные решения
432. Ухудшение графа
Вам дан неориентированный взвешенный граф на $n$ вершинах без кратных рёбер. От вас требуется убрать одно из рёбер графа таким образом, чтобы для максимального количества вершин расстояние от них до вершины с номером 1 изменилось.
Выведите максимально возможное количество вершин, для которых можно изменить расстояние до вершины 1 удалением одного ребра из графа.
Формат ввода
В первой строке вводится число $n$ ($1 \le n \le 300$) — количество вершин в графе.
В следующих $n$ строках вводится по $n$ чисел $a_{i,j}$ через пробел ($–1 \le a_{i,j} \le 100\,000$) — элементы матрицы смежности графа. $a_{i,j}$ равно:
- 0, если i = j,
- –1, если ребро между вершинами $i, j$ отсутствует,
- $> 0$, в любом другом случае.
Формат вывода
Выведите одно число — ответ на задачу.
Примечание
В первом тесте граф представляет из себя путь из 1 в 3 с промежуточной вершиной 2. Если удалить ребро из 1 в 2, то для вершин 2 и 3 кратчайшее расстояние от 1 до них изменится.
В третьем тесте вершина 1 изначально является изолированной, поэтому расстояние от нее до любой другой вершины не изменится с удалением ребра.
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
3
0 1 -1
1 0 1
-1 1 0
2
Пример 2
2
0 1
1 0
1
Пример 3
3
0 -1 -1
-1 0 1
-1 1 0
0
Пример 4
5
0 16 12 1 12
16 0 12 13 -1
12 12 0 5 2
1 13 5 0 2
12 -1 2 2 0
4