30147 - 最短路径
时间限制 : 1 秒
内存限制 : 256 MB
给定一个 n 个点的有向图，点的编号为 1 \sim n，对于任意两个不同的点 i \neq j，i 到 j 都有一条边，边权为 a_{i,j}。
在接下来 q 天，每天都会有一个节点 p_i 在当天关闭，你需要给出这一天 s_i 在不经过 p_i 的前提下，到达 t_i 的最短路径长度。
输入
第一行两个正整数 n, q（3 \le n \le 300，1 \le q \le 5 \times 10^5）表示有向图的节点数以及询问个数。
下面 n 行，每行 n 个整数，其中第 i 行第 j 个整数表示
a_{i,j}
（0 \le a_{i,j} \le 10^{14}，
a_{i,i} = 0）。
下面 q 行，每行三个整数 s_i, t_i, p_i（1 \le s_i, t_i, p_i \le n，s_i, t_i, p_i 互不相同），表示询问 s_i 在不经过 p_i 的前提下，到达 t_i 的最短路径长度。
输出
一共 q 行，每行一个整数表示答案。
样例
输入
3 3 0 7 8 14 0 5 8 16 0 3 2 1 1 3 2 2 1 3
输出
16 8 14
输入
5 8 0 15 8 7 8 8 0 8 6 8 8 7 0 14 7 5 7 6 0 14 12 8 7 6 0 4 3 5 4 5 1 5 1 4 4 5 3 1 2 4 2 3 5 3 4 2 3 4 5
输出
6 13 12 13 15 8 13 13
提示
- 对于 30\% 的测试点：n, q \le 100。
- 对于 50\% 的测试点：q \le 1000。
- 对于所有测试点：1 \le s_i, t_i, p_i \le n \le 300，1 \le q \le 5 \times 10^5，
0 \le a_{i,j} \le 10^{14}，
\forall 1 \le i \le n : a_{i,i} = 0。
来源
北大期末考试