← 返回题目列表

AtCoder · utpc2013_12

L. 1日元负载

中文机器翻译题面 查看原题

問題

背景

鳗鱼王国的邻国阿兔王国的前国王喜欢在道路上设置检查站。整个王国,每次我经过 1 还有一种方式可以用Usadol来收取通行税(Usadol是兔子王国的货币单位)。

现任国王阿兔想废除这一点,减轻人民负担,但前国王派系依然强大,很难推翻检查站。接受咨询的鳗鱼王国国王提出了一个创新的建议来解决这个问题。每当我经过一条没有检查站、前保皇派势力薄弱的道路时, 1 他们设立了一个“反向检查站”,Usador 的赏金被移交到这里。这样一来,路人的收入和支出就得以平衡,兔子王国也迎来了太平。

现在,生活在兔子王国的小兔子二郎,性格干净。他无法想象靠着国王的善意,通过反向关卡就能赚钱。即使绕了很长的路,或者意味着一遍又一遍地绕同一条路线,二郎也确保无论他走到哪里,检查站和反向检查站的总收入和支出都是相同的。 我决定走一条通往 ±0 的路线。

另一方面,二郎因为他干净的性格而很穷。当我要去某个地方时,我总是检查我的钱。 0 这是乌萨多。我希望你为 Jiro 编写一个最短路径计算程序。 编号为

課題

0 减去 N-1 编号的 N 给出了由顶点组成的有向图。该图的边具有正整数长度,并且以下3分为由以下字符表示的类型。

  • '-':“检查点”。每次经过,我的钱都会增加 1 减少。拥有的金钱 当 0 时,此类边不能通过。
  • '+':“反向检查点”。每次路过,我身上总有钱。 1 增加。
  • '=':一条普通道路,上面什么都没有。您拥有的金钱数量不会改变。

兔次郎有钱 顶点位于 0 偏离 0 ,最终金额 我想要到达 0 偏离 N-1 。找到这样一条路径的最短长度。沿着路线经过相同的顶点或边多少次并不重要。特别是除了第一个和最后一个顶点之外的顶点 您可以通过 0 和 按字典顺序比较 N-1 。

配点

300

入力

输入按以下格式给出。

N
G0
...
GN-1
L0,0 ... L0,N-1
...
LN-1,0 ... LN-1,N-1

N 是顶点数, 使用字符串Gi=Gi,0Gi,1...Gi,N−1 是长度 N 表示 Gi,j 是顶点 是 i 到顶点 j 的边类型。 Gi,j='x' 如果顶点 i 到顶点 j 没有边缘。Li,j 是一个自然数,0 如果顶点 i 到顶点 j 没有边,否则顶点 显示 i 到顶点 j 的边长。

制約

输入中的每个变量都满足以下约束。

  • 2\leq N\leq 250
  • 全部 i 关于 Gi,i='x'
  • 全部 i, j 关于 Gi,j='x' 如果 Li,j=0 ,否则 0\lt Li,j \lt 10,000

部分点

针对此问题设置了部分分数。这个问题的测试用例50这些点还满足以下约束。

  • 2 \leq N \leq 50

出力

问题的解决办法 在1行输出。如果没有满足条件的路线, 输出 -1 。

入力例1

5
x+x=x
xx-xx
x+x+-
xxxx-
xxxxx
0 1 0 1 0
0 0 1 0 0
0 1 0 1 1
0 0 0 0 1
0 0 0 0 0
図 1: 入力例1的图表

输入示例 1 的输出示例 路径

4

頂点0(所持金0) → 頂点1(所持金1) → 頂点2(所持金0) → 頂点3(所持金1) → 頂点4(所持金0)是解决方案。如果路线比这个短,到达终点时你所拥有的金钱将为 它不会变成0。

入力例2

4
x+=x
+xxx
=xx-
xx-x
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0
図 2: 入力例2的图表

输入示例 2 的输出示例

-1

从起点到终点有一条路线,但钱只是 在状态0下不可能到达终点。

入力例3

3
x--
=x+
==x
0 58 58
42 0 58
42 42 0

输入示例 3 的输出示例

-1

頂点1出来的所有面都是“-”,所以你有多少钱0无法移动。

入力例4

8
x+xxxxxx
xx+x=xxx
+xxxxxxx
xxxx-xxx
xxxxx-xx
xxxxxx-x
xxxxxxx-
xxx-xxxx
0 1 0 0 0 0 0 0
0 0 2 0 3 0 0 0
4 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 4 0 0
0 0 0 0 0 0 3 0
0 0 0 0 0 0 0 2
0 0 0 1 0 0 0 0
図 3: 入力例4的图表

输入示例 4 的输出示例

71

您可能会多次经过起点、终点或每一边。