Sem_2_Task_5

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

struct Edge;

const size_t INF = size_t(1e12);

namespace {
    using NumsVec = std::vector<int64_t>;
    using VecNumsVec = std::vector<NumsVec>;
    using BoolVec = std::vector<bool>;
    using EdgeVec = std::vector<Edge>;
}

struct Edge {
    Edge() = default;
    Edge(std::pair<size_t, size_t> edge) : from(edge.first), to(edge.second) {};
    Edge(size_t i, size_t j, size_t w, size_t u) : from(i), to(j) {};

    bool operator==(const Edge& other) const {
        return from == other.from && to == other.to;
    }

    size_t from = 0;
    size_t to = 0;
};

std::istream& operator>>(std::istream& input, Edge& p) {
    input >> p.from >> p.to;
    --p.from;
    --p.to;
    return input;
}

void InputEdges(std::vector<Edge>& edges) {
    for (auto& edge : edges) {
        std::cin >> edge;
    }
}

template<>
struct std::hash<Edge> {
    size_t operator()(const Edge& p) const {
        return p.from * p.to;
    }
};

std::ostream& operator<<(std::ostream& output, NumsVec& vec) {
    for (auto elem : vec) {
        std::cout << elem + 1 << " ";
    }
    return output;
}

struct Graph {
    Graph(size_t n) : size(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, INF) {};

    Graph(size_t n, EdgeVec& edges) : size(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, INF) {
        for (auto edge : edges) {
            matrix[edge.from][edge.to] = true;
        }
    };

    Graph(size_t n, VecNumsVec& matr, NumsVec& order) : size(n), matrix(matr), order(order), sums(n, 0) {};

    size_t size = 0;
    bool cycle = false;

    VecNumsVec matrix;
    BoolVec visited;
    NumsVec color;
    NumsVec top_sort;
    NumsVec d;
    NumsVec order;
    NumsVec sums;
    size_t top_sort_pos = 0;
};

void Floyd(Graph& g) {
    for (size_t k = 0; k < g.size; ++k) {
        size_t xk = g.order[k];
        for (size_t i = 0; i < g.size; ++i) {
            for (size_t j = 0; j < g.size; ++j) {
                size_t u = g.order[i];
                size_t v = g.order[j];
                g.matrix[u][v] = std::min(g.matrix[u][v], g.matrix[u][xk] + g.matrix[xk][v]);
                if (i <= k && j <= k) {
                    g.sums[k] += g.matrix[u][v];
                }
            }
        }
    }
}

int main() {
    size_t n;
    std::cin >> n;
    VecNumsVec matr(n, NumsVec(n, 0));
    for (size_t i = 0; i < n; ++i) {
        for (size_t j = 0; j < n; ++j) {
            std::cin >> matr[i][j];
        }
    }
    NumsVec order(n);
    for (auto& x : order) {
        std::cin >> x;
        --x;
    }
    std::reverse(order.begin(), order.end());
    Graph g(n, matr, order);
    Floyd(g);
    std::reverse(g.sums.begin(), g.sums.end());
    for (size_t v = 0; v < n; ++v) {
        std::cout << g.sums[v] << " ";
    }
}