C. Дейкстра без кучи: обратно

Как классная задача C, но найдите расстояния до вершины 1 из каждой вершины, а не от неё.

Отдельного алгоритма для этого нет и не нужно. Разверните все рёбра — то есть транспонируйте матрицу, — и запустите ту же Дейкстру за $O(n^2)$ из вершины 1. Расстояние от вершины 1 в развёрнутом графе равно расстоянию до вершины 1 в исходном.

Транспонирование матрицы — это b[j][i] = a[i][j]. Легко перепутать индексы; проверяйте на примере, где ответ несимметричен.

Первая строка содержит число $n$ ($1 \le n \le 1000$).

Далее идут $n$ строк по $n$ чисел — матрица смежности ориентированного графа. $-1$ означает отсутствие ребра, вес не превосходит $10^4$, на главной диагонали нули.

Одна строка из $n$ чисел: расстояния до вершины 1 или $-1$.