4.危险系数（danger）

题目描述

FJ在一条船上，海上有N(1<=N<=100)个岛，编号为1…N，现在他的任务是按照一个给定的访问次序A_1,A_2,….A_M去探索这M(2<=M<=10,000)个岛屿，已经知道任意两个岛屿之间的危险系数，让你找出一个探索序列，只需满足你的探索序列包含给定的A_1…A_M这个序列就可以(不一定要连续)，使得总的危险系数最小。

输入

第1行：两个数, N 和 M
第 2…M+1行：第i+1行表示给定的序列中第i个岛屿A_i
第M+2…N+M+1行：每行N个整数，表示岛屿之间的危险系数，左对角线上一定是0。

输出

输出满足要求的最小危险系数

样例输入

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

样例输出

7

提示

我们可以按照1，3，2，3，1，3的顺序去探索，满足了规定了序列是该序列的字序列，危险系数为(1,3)+(3,2)+(2,3)+(3,1)+(1,3)=7。

正解
很简单的最短路
我用的是Floyd
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[10005],b[105][105];
long long s;
int main()
{
   
	freopen("danger.in","r",stdin);
	freopen("danger.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	 cin>>a[i];
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  cin>>b[i][j];
	for(int k=1;k<=n;k++)//Floyd标准五行
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)   
	   if(i!=j&&i!=k&&j!=k)
	    b[i][j]=min(b[i][j],b[i][k]+b[k][j]);
	for(int i=1;i<=m-1;i++)//将两个点的最小危险加起来
	 s+=b[a[i]][a[i+1]];
	cout<<s;     //输出和
	return 0;
}

下面附本次比赛的其它题目

2020.03.14模拟赛16（第一题）
2020.03.14模拟赛16（第二题）
2020.03.14模拟赛16（第三题）
2020.03.14模拟赛15（第四题）
2020.03.14模拟赛15（总结）

谢谢