| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
小可可和小多来到了一个网格图上进行最短路训练。
这是一个 n × n 的网格图，对于点 (x, y)，如果 y < n，则它向 (x, y + 1) 有一条有 向边，边权为 eax,y；如果 x < n，则它向 (x + 1, y) 有一条有向边，边权为 ebx,y。小可 可需要在很短的时间内找到从 (1, 1) 到 (n, n) 的最短路。
然而，小多会捣乱 q 次：小雪会删去图中的一条边，然后小可可就需要重新计算 (1, 1) 到 (n, n) 的最短路。当小可可计算完成后，小多就会恢复这条边。即：每次小多删 掉的边只会影响到这一次小可可的计算。
小可可坚持尝试不借助外力，自己每次计算出答案。可惜小可可不是机器人，没过 一会儿他就晕倒了。于是，计算最短路的任务就落到了你的头上。
为避免过大的输入量，网格图边的边权将在程序内生成。 第一行两个正整数 n, q，表示网格的大小和小多捣乱的次数。
第二行两个整数 seed 和 B，为辅助数据生成的变量。请保证它们为全局变量且 seed 是 64 位无符号整形变量。
接下来按照从第一行到第 n 行，第一列到第 n − 1 列的顺序生成 eai,j：每次生成时 先调用一次 xorshift64()，再将 eai,j 赋值为 seed&(2B − 1)。其中 & 表示二进制按位 且运算，xorshift64() 在选手目录下的 samples/walk/xorshift 中已经给出。
再接下来按照从第一行到第 n − 1 行，第一列到第 n 列的顺序生成 ebi,j：每次生成 时先调用一次 xorshift64()，再将 ebi,j 赋值为 seed&(2B − 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() 函数和程序读入/生成数据的顺序。
此数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。
4 4
10583998785722269293 2
2 2 2 3
2 3 3 3
1 2 2 2
1 1 1 2
5
4
7
9
数据规模与约定
对于 20% 的数据，满足 n, q ≤ 5, B = 1；
对于 40% 的数据，满足 n, q ≤ 300；
对于 70% 的数据，满足 n ≤ 300； 对于 100% 的数据，有 2 ≤ n ≤ 5000, 1 ≤ q ≤ 105 , 1 ≤ B ≤ 30, 1 ≤ x, y, x′ , y′ ≤ n。
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$ $ms] | |||
| 内存最少[$ $KB] | |||
| 第一AC | |||
| 第一挑战 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|