刷题总结——shortest（ssoi）

题目：

题目背景

SOURCE：NOIP2015-SHY-3

题目描述

给定一张 n 个点的有向带权完全图，和一个数组 a[] ，请按顺序删除数组中的点，请求出在删除点 a[i] 以前，所有未删除点对之间的最短路的值的和。

输入格式

第一行一个整数 n ，表示点数；
接下来 n 行，每行 n 个数构成邻接矩阵，描述每条边的权值，保证 i 号点到 i 号点的权值为 0 ；
最后一行 n 个小于等于 n 的不同的数，描述数组 a[]。

输出格式

输出 1 行 n 个数，表示答案。

样例数据 1

输入　 [复制]

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

备注

【数据范围】
对 30% 的输入数据：1≤n≤10 ；
对 100% 的输入数据：1≤n≤500；0＜权值≤100000 。

题解：

先转变成倒插入数字的问题，再用floyd算最短距离：n方算之前的插入的点到当前点的最短距离，和当前点到之前插入的点的最短距离，最后再用n方算经过当前点的路径的最短距离

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=;

long long dis[N][N];

int n,num[N],ans[N];

int main()

{

  //freopen("a.in","r",stdin);

  scanf("%d",&n);

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      scanf("%d",&dis[i][j]);

  for(int i=;i<=n;i++)

    scanf("%d",&num[i]);

  reverse(num+,num+n+);

  for(int i=;i<=n;i++)

  {

    if(i==)

    {

      ans[i]=;

      continue;

    }

    for(int k=;k<=i-;k++)

      for(int j=;j<=i-;j++)

      {

        dis[num[j]][num[i]]=min(dis[num[j]][num[i]],dis[num[j]][num[k]]+dis[num[k]][num[i]]);

        dis[num[i]][num[j]]=min(dis[num[i]][num[j]],dis[num[i]][num[k]]+dis[num[k]][num[j]]);

      }

    for(int k=;k<=i-;k++)

      for(int j=;j<=i-;j++)

        dis[num[k]][num[j]]=min(dis[num[k]][num[j]],dis[num[k]][num[i]]+dis[num[i]][num[j]]);

    for(int k=;k<=i;k++)

      for(int j=;j<=i;j++)

        ans[i]+=dis[num[k]][num[j]];

  }

  for(int i=n;i>=;i--)

    cout<<ans[i]<<" ";

  return ;

}

巴特西