U291531 [ACSP-J 2023] 行走

**本题暂无数据**

小可可和小多来到了一个网格图上进行最短路训练。 这是一个 $n \times n$ 的网格图，对于点 $(x, y)$，如果 $y < n$，则它向 $(x, y + 1)$ 有一条有 向边，边权为 $ea_{x,y}$；如果 $x < n$，则它向 $(x + 1, y)$ 有一条有向边，边权为 $eb_{x,y}$。小可 可需要在很短的时间内找到从 $(1, 1)$ 到 $(n, n)$ 的最短路。 然而，小多会捣乱 $q$ 次：小多会删去图中的一条边，然后小可可就需要重新计算 $(1, 1)$ 到 $(n, n)$ 的最短路。当小可可计算完成后，小多就会恢复这条边。即：每次小多删 掉的边只会影响到这一次小可可的计算。 小可可坚持尝试不借助外力，自己每次计算出答案。可惜小可可不是机器人，没过一会儿他就晕倒了。于是，计算最短路的任务就落到了你的头上。

**为避免过大的输入量，网格图边的边权将在程序内生成。** 第一行两个正整数 $n, q$，表示网格的大小和小多捣乱的次数。 第二行两个整数 $seed$ 和 $B$，为辅助数据生成的变量。**请保证它们为全局变量且 $seed$ 是 64 位无符号整形变量**。 接下来按照从第一行到第 $n$ 行，第一列到第 $n − 1$ 列的顺序生成 $ea_{i,j}$：每次生成时先调用一次 `xorshift64()`，再将 $ea_{i,j}$ 赋值为 $seed\&(2^B − 1)$。其中 & 表示二进制按位与运算，`xorshift64()` 在选手目录下的 `samples/walk/xorshift` 中已经给出。 再接下来按照从第一行到第 $n − 1$ 行，第一列到第 $n$ 列的顺序生成 $eb_{i,j}$：每次生成 时先调用一次 `xorshift64()`，再将 $eb_{i,j}$ 赋值为 $ seed\&(2^B − 1)$。 请严格按照上述过程生成数据，中途不能自行改变 $seed$ 和 $B$ 的值，否则数据将错误生成。 接下来 $q$ 行，每行四个整数 $x, y, x′ , y′$，表示小多捣乱删掉的一条边。保证 $x′ = x, y′ = y + 1$ 或 $y′ = y, x′ = x + 1$。 如果你仍不会生成数据，选手目录下的 `samples/walk/sample.cpp` 已经实现好了所 有的数据读入/生成，你可以直接使用在你的代码中。再次提醒，请不要自行改动 $seed，B，$`xorshift64()` 函数和程序读入/生成数据的顺序。 此数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出 $q$ 行，每行一个整数，表示删掉给定边后 $(1, 1)$ 到 $(n, n)$ 的最短路。

数据规模与约定： - 对于 $20\%$ 的数据，满足 $n, q \le 5, B = 1$； - 对于 $40\%$ 的数据，满足 $n, q \le 300$； - 对于 $70\%$ 的数据，满足 $n \le 300$； - 对于 $100%$ 的数据，有 $2 \le n \le 5000, 1 \le q \le 10^5, 1 \le B \le 30, 1 \le x, y, x′, y′ \le n$。 “科大国创杯”2023 年安徽省青少年信息学科普日活动 ACSP-J 组 T3