| Codeforces Round 179 (Div. 1) |
|---|
| Закончено |
У Егора есть взвешенный ориентированный граф, состоящий из n вершин. В этом графе между любой парой различных вершин есть ребро в обоих направлениях. Егор любит играть с графом, и сейчас он придумал новую игру:
- Игра состоит из n шагов.
- На i-том шаге Егор удаляет из графа вершину номер xi. Удаляя вершину, Егор удаляет все ребра, которые входили в данную вершину и которые выходили из нее.
- Перед выполнением каждого шага, Егор хочет знать сумму длин кратчайших путей между всеми парами оставшихся вершин. Кратчайший путь может проходить через любую оставшуюся вершину. Другими словами, если обозначить как d(i, v, u) кратчайший путь между вершинами v и u в графе, который получился до удаления вершины xi, то Егор хочет знать значение следующей суммы:
.
Помогите Егору, выведите значение искомой суммы перед каждым шагом.
В первой строке содержится целое число n (1 ≤ n ≤ 500) — количество вершин в графе.
В следующих n строках содержится по n целых чисел — матрица смежности графа: j-тое число в i-той строке aij (1 ≤ aij ≤ 105, aii = 0) обозначает вес ребра, ведущего из вершины i в вершину j.
В следующей строке содержится n различных целых чисел: x1, x2, ..., xn (1 ≤ xi ≤ n) — вершины, которые удаляет Егор.
Выведите n целых чисел — i-тое число равно искомой сумме перед i-тым шагом.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
1
0
1
0
2
0 5
4 0
1 2
9 0
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
17 23 404 0
