一次折扣路线

难度：T4

【知识点：分层最短路】

前置知识：非负权Dijkstra、long long、资源状态。

题目描述与输入

首行 $n,m,s,t$，随后 $m$ 行有向边 $u,v,w,c$，允许重边和自环。$c=1$ 表示该道路允许优惠，$c=0$ 表示不允许。必须在实际走过的一条允许优惠的道路上恰好使用一次券，该次通行费用为向下取整的 $w/2$；其他通行按原价。允许重复经过顶点和道路。求合法路线的最小费用。即使 $s=t$，没有使用券的空路线也不合法。

输出格式

输出最小费用；不存在合法路线输出 $-1$。

数据范围

$1\le n\le100$，$0\le m\le1000$，$0\le w\le10^9$，$c\in\{0,1\}$，顶点编号在 $[1,n]$ 内。

样例输入

3 3 1 3
1 3 8 0
1 2 5 1
2 3 1 0

样例输出

3

样例解释

直达边不允许优惠，不能作为合法答案。走 $1$ 到 $2$ 时使用券，费用为 $2$，再到 $3$ 花费 $1$，合计 $3$。