1511 : 星际走私客的跃迁网络

时间限制Time Limit 1 秒Sec 内存限制Memory Limit 512 兆MB 提交次数Submitted 0 次Times 通过次数Solved 0 次Times 标准评测Standard Judge

题目描述Description

在遥远的银河系中，有 N 个星系（编号 1 \sim N）。每个星系都有一个独特的“空间稳定度” A_i（保证所有星系的 A_i 互不相同）。星系之间被一张密集的古老星门网络连接，任意两个星系 u, v 之间都有一条基础能量消耗为 W_{u,v} 的航道（如果没有直接航道则为 -1）。

你是一名星际走私客，需要驾驶飞船从星系 S 前往星系 T。你的飞船使用的是一种极其不稳定的“量子跃迁引擎”。一次完整的「量子跃迁」可以从星系 u 移动到星系 v (u \neq v)，但在跃迁过程中，飞船可能会在折叠空间中经过若干个中间星系。

为了保证飞船不在跃迁中解体，引擎的安全协议有着严苛的限制：

单次「量子跃迁」中，飞船所经过的所有“中间星系” x，其空间稳定度必须严格小于起点 u 和终点 v 的空间稳定度。 （即对于路径上任意中间节点 x，必须满足 A_x < \min(A_u, A_v)）。

单次跃迁的能量消耗，等于该次跃迁在星门网络中实际走过航道的基础能量消耗之和。

引擎的散热系统要求你在到达终点前，必须且只能进行恰好 K 次「量子跃迁」（每次跃迁必须改变所在星系，不能原地跃迁）。

接下来, Q次询问, 请问从星系 S 到星系 T 恰好进行 K 次跃迁的最小总能量消耗是多少？如果无法到达，请输出 -1。

第一行两个整数：N, K。

第二行 N 个整数：A_1, A_2, \dots, A_N 表示各个星系的空间稳定度。

接下来 N 行，每行 N 个整数，给出一个矩阵 W，W_{i,j} 表示星系 i 到 j 的单条航道基础能量消耗（W_{i,i} = 0，无航道为-1）。

然后一行一个整数 Q，表示询问数量。

接下来 Q 行，每行两个整数 S, T，表示一次询问。

输出 Q 行，每行一个整数。

如果能够从星系 S 经过恰好 K 次「量子跃迁」到达星系 T，则输出所需的最小总能量消耗。

如果由于航道限制或引擎协议（无法满足中间节点 A_x < \min(A_u, A_v) 的约束）导致无法在恰好 K 次跃迁内到达，则输出 -1。

Ldawn_AI

深圳技术大学第六届程序设计竞赛