{"trustable":false,"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":"\u003cp\u003e一个国家有 $n$ 座城市,每个城市之间可能有一条公路或没有。现在有一些货物要从一座城市运输到另一座城市。交通费用由两部分组成:\n\n\u003cp\u003e1、在公路上的运输成本\n\n\u003cp\u003e2、固定的税收,每经过一座城市需要上缴一定的费用,费用可能不同,源城市和目标城市不用交。\n\n\u003cp\u003e现在请你编写一个程序计算出最短路径和花费。"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e本题有多组数据。\n\n\u003cp\u003e每组数据的第一行是一个数字 $n$,表示有 $n$ 座城市,$n\u003d0$ 表示数据结束。\n\t\n\u003cp\u003e然后是一个 $n \\times n$ 行,用来表示任意两座城市之间公路的花销,$-1$ 代表没有公路。\n\n\u003cp\u003e然后是一行 $n$ 个数字,表示从每座城市中转时的固定税收。\n\n\u003cp\u003e接下来若干行,每行 $2$ 个数 $c, d$ 表示询问从 $c$ 到 $d$ 的最短路径。以 $-1$ 结尾。"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出格式\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\nFrom c to d :\nPath: c--\u003ec1--\u003e......--\u003eck--\u003ed\nTotal cost : ......\n......\n\nFrom e to f :\nPath: e--\u003ee1--\u003e......--\u003eek--\u003ef\nTotal cost : ......\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003cp\u003e对每个询问输出一组,如果有多个最短路径,输出字典序最小的一个。每输出完一组输出一个空行。\n\n\u003cp\u003e具体参见样例。"}},{"title":"Sample 1","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\n0 3 22 -1 4\n3 0 5 -1 -1\n22 5 0 9 20\n-1 -1 9 0 4\n4 -1 20 4 0\n5 17 8 3 1\n1 3\n3 5\n2 4\n-1 -1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eFrom 1 to 3 :\nPath: 1--\u0026gt;5--\u0026gt;4--\u0026gt;3\nTotal cost : 21\n\nFrom 3 to 5 :\nPath: 3--\u0026gt;4--\u0026gt;5\nTotal cost : 16\n\nFrom 2 to 4 :\nPath: 2--\u0026gt;1--\u0026gt;5--\u0026gt;4\nTotal cost : 17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}