{"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":"\u003cdiv class\u003d\"panel_content\"\u003e\n\t\u003cp\u003e\n\t\t\u003cspan data-scayt_word\u003d\"一个国家有N座城市,每个城市之间可能有一条公路或没有。现在有一些货物要从一座城市运输到另一座城市。交通费用由两部分组成\" data-scaytid\u003d\"15\"\u003e一个国家有N座城市,每个城市之间可能有一条公路或没有。现在有一些货物要从一座城市运输到另一座城市。交通费用由两部分组成\u003c/span\u003e:\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:39.0pt;\"\u003e\n\t\t1.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003cspan data-scayt_word\u003d\"在公路上的运输成本\" data-scaytid\u003d\"16\"\u003e在公路上的运输成本\u003c/span\u003e\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:39.0pt;\"\u003e\n\t\t2.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003cspan data-scayt_word\u003d\"固定的税收,每经过一座城市需要上缴一定的费用,费用可能不同,源城市和目标城市不用交。\" data-scaytid\u003d\"17\"\u003e固定的税收,每经过一座城市需要上缴一定的费用,费用可能不同,源城市和目标城市不用交。\u003c/span\u003e\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:21.0pt;\"\u003e\n\t\t\u003cspan data-scayt_word\u003d\"现在请你编写一个程序计算出最短路径和花费。\" data-scaytid\u003d\"18\"\u003e现在请你编写一个程序计算出最短路径和花费。\u003c/span\u003e\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n\t\u003cp\u003e\n\t\t\u003cspan data-scayt_word\u003d\"本题有多组数据。第一行是一个数字n\" data-scaytid\u003d\"19\"\u003e本题有多组数据。第一行是一个数字n\u003c/span\u003e,\u003cspan data-scayt_word\u003d\"表示有n座城市,n\" data-scaytid\u003d\"20\"\u003e表示有n座城市,n\u003c/span\u003e\u003d\u003cspan data-scayt_word\u003d\"0表示数据结束。\" data-scaytid\u003d\"21\"\u003e0表示数据结束。\u003c/span\u003e\u003c/p\u003e\n\t\u003cp\u003e\n\t\t\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003cspan data-scayt_word\u003d\"然后是一个n\" data-scaytid\u003d\"22\"\u003e然后是一个n\u003c/span\u003e\u0026times;\u003cspan data-scayt_word\u003d\"n行,用来表示任意两座城市之间公路的花销,-1代表没有公路。\" data-scaytid\u003d\"23\"\u003en行,用来表示任意两座城市之间公路的花销,-1代表没有公路。\u003c/span\u003e\u003c/p\u003e\n\t\u003cp\u003e\n\t\t\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003cspan data-scayt_word\u003d\"然后是一行n个数字,表示从每座城市中转时的固定税收。\" data-scaytid\u003d\"24\"\u003e然后是一行n个数字,表示从每座城市中转时的固定税收。\u003c/span\u003e\u003c/p\u003e\n\t\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003cspan data-scayt_word\u003d\"接下来若干行,每行2个数c,d表示询问从c到d的最短路径。以-1\" data-scaytid\u003d\"25\"\u003e接下来若干行,每行2个数c,d表示询问从c到d的最短路径。以-1\u003c/span\u003e \u003cspan data-scayt_word\u003d\"-1结尾。\" data-scaytid\u003d\"26\"\u003e-1结尾。\u003c/span\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n\t\u003cp\u003e\n\t\t\u003cspan data-scayt_word\u003d\"输出格式\" data-scaytid\u003d\"27\"\u003e输出格式\u003c/span\u003e\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:21.0pt;\"\u003e\n\t\tFrom c to d :\u003cbr /\u003e\n\t\tPath: c--\u0026gt;c1--\u0026gt;......--\u0026gt;ck--\u0026gt;d\u003cbr /\u003e\n\t\tTotal cost : ......\u003cbr /\u003e\n\t\t......\u003cbr /\u003e\n\t\t\u003cbr /\u003e\n\t\tFrom e to f :\u003cbr /\u003e\n\t\tPath: e--\u0026gt;e1--\u0026gt;..........--\u0026gt;ek--\u0026gt;f\u003cbr /\u003e\n\t\tTotal cost : ......\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:21.0pt;\"\u003e\n\t\t\u003cspan data-scayt_word\u003d\"对每个询问输出一组,如果有多个最短路径,输出字典序最小的一个。每输出完一组输出一个空行。\" data-scaytid\u003d\"28\"\u003e对每个询问输出一组,如果有多个最短路径,输出字典序最小的一个。每输出完一组输出一个空行。\u003c/span\u003e\u003c/p\u003e\n\t\u003cp style\u003d\"margin-left:21.0pt;\"\u003e\n\t\t\u003cspan data-scayt_word\u003d\"具体参见样例。\" data-scaytid\u003d\"29\"\u003e具体参见样例。\u003c/span\u003e\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n\t\u003cpre\u003e\n\t\u003c/pre\u003e\n\t\u003cdiv style\u003d\"font-family:Courier New,Courier,monospace;\"\u003e\n\t\t\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\u003c/pre\u003e\n\t\u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n\t\u003cpre\u003e\n\t\u003c/pre\u003e\n\t\u003cdiv style\u003d\"font-family:Courier New,Courier,monospace;\"\u003e\n\t\t\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\u003c/pre\u003e\n\t\u003c/div\u003e\n\u003c/div\u003e"}}]}