{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e这是 Spring 国家中的 N 个城市。每对城市之间可能有一条或没有交通路径。现在有一些货物需要从一个城市运送到另一个城市。运输费用包括两部分:\u003cbr\u003e这些城市之间路径上的运输费用,以及\u003cbr\u003e\u003cbr\u003e一定的税收,每当有货物通过一个城市时就会收取,除了起点和终点城市。\u003cbr\u003e\u003cbr\u003e你必须编写一个程序来找到具有最小成本的路径。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"首先是 N,表示城市数量。当 N \u003d 0 时表示输入结束。\u003cbr\u003e\u003cbr\u003e输入中给出了路径成本、城市税收、起点和终点城市的数据,格式如下:\u003cbr\u003e\u003cbr\u003ea11 a12 ... a1N\u003cbr\u003ea21 a22 ... a2N\u003cbr\u003e...............\u003cbr\u003eaN1 aN2 ... aNN\u003cbr\u003eb1 b2 ... bN\u003cbr\u003e\u003cbr\u003ec d\u003cbr\u003ee f\u003cbr\u003e...\u003cbr\u003eg h\u003cbr\u003e\u003cbr\u003e其中 aij 表示从城市 i 到城市 j 的运输成本,aij \u003d -1 表示城市 i 和城市 j 之间没有直接路径。bi 表示通过城市 i 的税收。货物需要从城市 c 到城市 d 运送,从城市 e 到城市 f 运送,...,g \u003d h \u003d -1。你必须输出经过的城市序列和总成本,格式如下:\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"从 c 到 d:\u003cbr\u003e路径:c--\u0026gt;c1--\u0026gt;......--\u0026gt;ck--\u0026gt;d\u003cbr\u003e总成本:......\u003cbr\u003e......\u003cbr\u003e\u003cbr\u003e从 e 到 f:\u003cbr\u003e路径:e--\u0026gt;e1--\u0026gt;..........--\u0026gt;ek--\u0026gt;f\u003cbr\u003e总成本:......\u003cbr\u003e\u003cbr\u003e注意:如果存在多条最小路径,输出字典序最小的路径。在每个测试用例后打印一个空行。\u003cbr\u003e\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n0 3 22 -1 4\r\n3 0 5 -1 -1\r\n22 5 0 9 20\r\n-1 -1 9 0 4\r\n4 -1 20 4 0\r\n5 17 8 3 1\r\n1 3\r\n3 5\r\n2 4\r\n-1 -1\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eFrom 1 to 3 :\r\nPath: 1--\u0026gt;5--\u0026gt;4--\u0026gt;3\r\nTotal cost : 21\r\n\r\nFrom 3 to 5 :\r\nPath: 3--\u0026gt;4--\u0026gt;5\r\nTotal cost : 16\r\n\r\nFrom 2 to 4 :\r\nPath: 2--\u0026gt;1--\u0026gt;5--\u0026gt;4\r\nTotal cost : 17\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}