==== 题面描述 ====
一个 $n$ 个点的有向图，给其邻接矩阵，现在可以是一对 $a_{i,j},a_{j,i}$ 均变为 $0$ ，求按顺序走过长度为 $k$ 的点列的最短时间。

$n \le 500, k \le 10^6$
==== 题解 ====
考虑先预处理出来点对间的最短路，和相邻点对出现的次数，之后分析一对 $i,j$ 变化后带来的影响。

对于一对相邻点对 $s,t$ ，变化带来的影响是 $c(s,t)*max(0,dis(s,t)-dis(s,i)-dis(j,t),dis(s,t)-dis(s,j)-dis(i,t))$ 。注意到后面两项不可能都大于 $0$ ，所以可以分别和 $0$ 取较大之后再加起来。

然后考虑将 $dis(s,i)$ 对 $i$ 排序，$dis(j,t)$ 对 $j$ 排序，之后枚举 $s,t$ 利用双指针和差分来实现对每对 $(i,j)$ 的答案，之后取最大值即可。