最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 问题 AC: L15-3 多维动态规划 - 练习9

    正文概述 网友投稿   2026-01-22 16:08:28  

    题目描述

    有小帅,小美,大聪明分别在1、2、3位置上, 每次移动需要花费时间,从位置a移动到位置b需要花费k(a,b)的时间。不移动不需要花费(即k(i,i)=0)但不保证k(a,b)=k(b,a)。 现在国王会开启n次开关,第i次开启的开关在pi处,国王每开启一个开关时都需要派一名队员到位置pi,过程中不能去其他地方,也就是必须直接过去。求小队的最小花费时间。

    输入

    第一行有两个数l,n(3<=l<=100,1<=n<=500)。 接下来的l行中的每一行都包含l个非负整数。其中第i+1行第j个数是k(i,j),表示花费时间(0<=k(i,j)<1000)。 最后一行,有n个整数,分别为p1、p2、p3、...、pn​表示国王开启开关的位置(1<=pi<=l)。

    输出

    一行一个数,表示最小花费时间。

    样例输入

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

    样例输出

    5
    信息学奥赛网,一个优质的源码资源平台!
    信息学奥赛网 » 问题 AC: L15-3 多维动态规划 - 练习9