最高分数: 1150 积分
任务说明已更新。
有 $N$ 箭头。起点为$(a_i,b_i)$的箭头,方向为$c_i$,大小为$d_i$。 ($d_i$ 可能为负数)
保证不存在两个起点相同的箭头。
所以想用箭头从单元格 $(sx,sy)$ 移动到单元格 $(gx,gy)$。
但可能无法移动到初始网格中的目标。
所以,Snuke 决定改变一些箭头。
因此可以按如下方式更改每个箭头:
他无法添加或删除箭头。
请计算他可以移动到 $(gx,gy)$ 的最低成本。
任务说明已更新。
问题陈述
有一个网格,其大小为$H \times W$。左上角的单元格是$(1,1)$,右下角的单元格是$(H,W)$。有 $N$ 箭头。起点为$(a_i,b_i)$的箭头,方向为$c_i$,大小为$d_i$。 ($d_i$ 可能为负数)
保证不存在两个起点相同的箭头。
所以想用箭头从单元格 $(sx,sy)$ 移动到单元格 $(gx,gy)$。
但可能无法移动到初始网格中的目标。
所以,Snuke 决定改变一些箭头。
- 他无法改变这个箭头的起点。
- 如果他改变这个箭头的方向,需要花费$e_i$。
- 如果他改变,成本为 $f \times |d_i-G|$ d_i 至 $G$。
他无法添加或删除箭头。
请计算他可以移动到 $(gx,gy)$ 的最低成本。
如果他无法移动到球门,请输出“-1”。
注意:箭头是有方向的,他不能在箭头中间转弯。输入
输入由以下格式的标准输入给出。H W N f sx sy gx gy a_1 b_1 c_1 d_1 e_1 a_2 b_2 c_2 d_2 e_2 : : : a_N b_N c_N d_N e_N
输出
- 请输出一个整数:解决此难题的最低成本。
- 如果无法实现目标,请打印
-1. - 打印
\n(换行)最后。
约束
- $1 \le H,W \le 100000$
- $1 \le N \le 70000$
- $1 \le f,e_i \le 1000000$
- $1 \le d_i \le 100000$
- $1 \le a_i,sx,tx \le H$
- $1 \le b_i,sy,ty \le W$
- $c_i$ 是
N,E,S,或W,表示北、东、南、西。
子任务
子任务 1 [ 190 点 ]
- $H=1$
- $W \le 600$
子任务 2 [ 170 点 ]
- $H,W \le 80$
子任务 3 [ 360 点 ]
- $H,W \le 600$
子任务 4 [ 430 点 ]
- 没有额外的限制。
示例输入 1
4 4 2 2 1 1 2 2 1 1 E 1 1 1 2 E 2 2
示例输出 1
4
示例输入 2
1 4 2 10 1 1 1 4 1 1 E 1 4 1 3 W 1 4
示例输出 2
14
示例输入 3
1 8 4 9 1 3 1 6 1 1 E 7 2 1 8 W 7 5 1 3 W 2 5 1 6 E 2 8
示例输出 3
14
示例输入 4
5 5 7 10 1 2 4 5 1 2 E 2 6 2 3 S 2 7 3 1 N 1 8 3 2 W 1 10 4 1 E 4 12 5 5 N 3 13 5 1 E 2 14
示例输出 4
14