{"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许多计算机科学领域都涉及需要通过某个域的最小路径的问题。例如,在VLSI布线问题中的一个约束是最小化电线长度。旅行推销员问题(TSP)——找出是否可以在指定的旅行时间限制内恰好访问推销员路线中的所有城市——是NP完全问题的经典示例之一;解决方案似乎需要大量时间生成,但检查起来很简单。\u003cbr\u003e\u003cbr\u003e这个问题涉及在穿越点阵时只能从左到右找到最短路径。\u003cbr\u003e\u003cbr\u003e给定一个m*n的整数矩阵,你需要编写一个程序来计算最小权重的路径。路径可以从第1列(第一列)的任意位置开始,并由一系列步骤组成,最终在第n列(最后一列)结束。一步包括在相邻(水平或对角线)行中从第i列移动到第i+1列。矩阵的第一行和最后一行(第1行和第m行)被视为相邻,即矩阵“环绕”,因此它表示一个水平圆柱体。合法的步骤如下图所示。\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/022ee4c6101ca794ffd90f7070f5f140?v\u003d1713512986\"\u003e\u003cbr\u003e\u003cbr\u003e路径的权重是访问的矩阵中每个n个单元格中整数的总和。\u003cbr\u003e\u003cbr\u003e例如,下面显示了两个略有不同的5*6矩阵(唯一的区别是底行中的数字)。\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/ef13810aed41e781fa4937f49c035392?v\u003d1713512986\"\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e对于每个矩阵都说明了最小路径。请注意,右侧矩阵的路径利用了第一行和最后一行的相邻性质。\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入由一系列矩阵规格说明组成。每个矩阵规格由一行中按顺序给出的行和列维度组成,后跟m是行维度,n是列维度的整数。整数按行主序出现在输入中,即前n个整数构成矩阵的第一行,接下来的n个整数构成第二行,依此类推。一行上的整数将与其他整数用一个或多个空格分隔开。注意:整数不限于为正数。输入文件中将会有一个或多个矩阵规格。输入以文件结尾结束。\u003cbr\u003e\u003cbr\u003e对于每个规格,行数将在1到10之间(包括1和10);列数将在1到100之间(包括1和100)。没有路径的权重将超过使用30位可表示的整数值\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于输入文件中的每个矩阵规格,应输出两行,第一行表示最小权重路径,第二行是最小路径的成本。路径包括一系列n个整数(用一个或多个空格分隔),表示构成最小路径的行。如果有多条最小权重路径,则应输出字典序最小的路径。\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 6\r\n3 4 1 2 8 6\r\n6 1 8 2 7 4\r\n5 9 3 9 9 5\r\n8 4 1 3 2 6\r\n3 7 2 8 6 4\r\n5 6\r\n3 4 1 2 8 6\r\n6 1 8 2 7 4\r\n5 9 3 9 9 5\r\n8 4 1 3 2 6\r\n3 7 2 1 2 3\r\n2 2\r\n9 10 9 10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 4 4 5\r\n16\r\n1 2 1 5 4 5\r\n11\r\n1 1\r\n19\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}