問題
背景
鳗鱼王国的邻国阿兔王国的前国王喜欢在道路上设置检查站。整个王国,每次我经过 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 的输出示例 路径
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 的输出示例
-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
输入示例 4 的输出示例
71
您可能会多次经过起点、终点或每一边。