// 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;
}
标签:insert,include,游戏,idx,int,顶点,删点,502
From: https://www.cnblogs.com/itdef/p/18362833