20200314 jzoj 危险系数(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

20200314 jzoj 危险系数(danger)

    **题解:
    使用Floyd算每个岛屿之间的最小的系数,最后ans统计就好。**

#include
#include
#include
long long f[200][200],a[210000],i,j,n,m,k;
long long ans;
using namespace std;
int main()
{
freopen(“danger.in”,“r”,stdin);
freopen(“danger.out”,“w”,stdout);
scanf("%lld%lld",&n,&m);
for(i=1;i<=m;i++)
scanf("%lld",&a[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%lld",&f[i][j]);
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=k&&i!=j&&j!=k)
f[i][j]=min(f[i][j],(f[i][k]+f[k][j]));
ans = 0;
for(i=1;i<m;i++)
ans=ans+f[a[i]][a[i+1]];
printf("%d",ans);
}

上一篇:CF1098D


下一篇:第八周实验报告和课程总结