← 返回题目列表

AtCoder · s8pc_4_f

F. 找到路线!

中文机器翻译题面 查看原题
最高分数: 1150 积分
任务说明已更新。

问题陈述

有一个网格,其大小为$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