#P10430. [2021年联测]god的怒火

    ID: 9548 传统题 1500ms 512MiB 尝试: 10 已通过: 1 难度: 7 上传者: 标签>图论数据结构队列CF2200BFS排序数学二分图最短路

[2021年联测]god的怒火

God 的怒火(anger)

题目描述

有一个 nn 行 mm 列的座位网格,你位于 (s,t)(s,t)。其中有 kk 个不能落脚的位置,均不等于起点。

一次跳跃可以到达与当前位置同行或同列的任意其他位置,可以跨越禁止位置,但不能落在禁止位置上。

对每个可以到达的其他非禁止位置,求从 (s,t)(s,t) 到它的最少跳跃次数,再将这些次数相加。不可达位置不计入答案。

输入格式

第一行五个整数 n,m,k,s,tn,m,k,s,t。

接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示一个禁止落脚的位置。

输出格式

输出一个整数,表示最少跳跃次数之和。保证答案在有符号 64 位整数范围内。

样例 1 输入

3 4 3 3 1
1 1
2 3
3 4

样例 1 输出

14

样例说明

到 (2,1),(3,2),(3,3)(2,1),(3,2),(3,3) 各需一步;到 (1,2),(1,3),(2,2),(2,4)(1,2),(1,3),(2,2),(2,4) 各需两步;到 (1,4)(1,4) 需三步。总和为 3×1+4×2+1×3=143\times1+4\times2+1\times3=14。

数据范围

全部数据满足 1≤n,m≤1061\le n,m\le10^6,0≤k≤1060\le k\le10^6,1≤xi,s≤n1\le x_i,s\le n,1≤yi,t≤m1\le y_i,t\le m,(xi,yi)≠(s,t)(x_i,y_i)\ne(s,t)。

测试点 附加限制
1—4 n,m≤1000n,m\le1000
5、6 k≤1000k\le1000
7—10 无