AT_utpc2013_12.1円ロード

题目背景

兔子王国的前国王非常喜欢在道路上建造关卡，建造关卡的需要交1元的通行税。
现国王想废除这个，但是前国王派的势力根深蒂固，很难废除关卡。
鳗鱼王国国王提出了解决这个问题的建议：设置了给1元的“反关卡”，这样行人的收支平衡，兔子王国迎来了和平。
兔子的Jiro想以所持金0从顶点0出发，最终以所持金0到达顶点N-1。求出这样的路径的最短长度。在路径中可以多次通过相同的顶点和边。特别是，也可以反复通过顶点0和N-1。
给出了一个由编号为0到N-1的N顶点组成的有向图，该图的边具有正整数的长度，并且被分类为以下3种文字表示的类型。
'-':“关卡”，每通过一次持有金就会减少1。持有金0时这种类型的边不能通过。
'+'：“反关卡”，每次通过携带的钱一定会增加1。
'=':普通的道路.所持的钱没有变化。
'x':没有道路。
这是0元，希望你能帮Jiro编写最短路径计算程序。

第一行输入一个 $n$ ,表示顶点数。
接下来 $n$ 行字符串，表示 $i$ 到 $j$ 的路的类型。
接下来 $n$ 行字符串，表示 $i$ 到 $j$ 的路的长度。

输出一个数，表示需要走的最短路径长度，如果无法达成目标的话输出-1。

翻译来自CHGM