502 删点游戏

// 502 删点游戏.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
http://oj.daimayuan.top/course/14/problem/685

给你一张 n个顶点的有向简单图，顶点编号从 1到 n，我们要把所有顶点一个一个删完。
小蜗每次会删掉图中的一个顶点和所有与它相连的边，小蜗想知道每删去一个顶点之后图中所有点对的距离之和。

输入格式
第一行一个整数 n，表示顶点数。

接下来 n行，每行 n个整数，组成一个 n×n的矩阵 A表示这张图的邻接矩阵，矩阵第 i行第 j列表示 i号顶点到 j号顶点有一条边权为 A[i][j]的边。

接下来一行，输入 n个数 x1,x2,...,xn，代表删除顶点的顺序。

输出格式
输出一行 n个数依次表示删除了第 0个点（一个点都没删除）到第 n−1个点（图中还剩下一个点）后，图中所有剩下的点对的距离之和。

样例输入
2
0 5
4 0
1 2
样例输出
9 0
数据规模
对于所有数据，保证 2≤n≤300,1≤A[i][j]≤10000,A[i][i]=0,1≤xi≤n。
*/

#include <iostream>
#include <algorithm>
#include <memory.h>


using namespace std;


const int N = 305;
int d[N][N];
int n;
int c[N];


int main() 
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> d[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	int ans[N]; memset(ans, 0, sizeof ans);
	int insert[N]; memset(insert, 0, sizeof insert);
	for (int idx = n-1; idx >= 0; idx--) {
		int k = c[idx]; insert[k] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
				if (insert[i] && insert[j]) {
					ans[idx] += d[i][j];
				}
			}
		}
	}

	for (int i = 0; i < n;i++) {
		cout << ans[i] << " ";
	}

	return 0;
}