{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan style\u003d\"font-size:14px;\"\u003eLeyni参加了一场汽车比赛,这个比赛是在n个城市中进行的,城市的编号为1..n,而且任意两个城市之间都存在一条双向的路。官方要Leyni进行r回合比赛,在第i回合中,官方要求Leyni从城市si出发并在城市ti结束,并允许他在任何一个城市更换汽车,但是最多允许更换ki次。\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;\"\u003e官方为Leyni准备了m种汽车,这些汽车可能通过不同的道路不同的方向时需要不同的时间。\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;\"\u003e请帮助Leyni计算对应每一回合,他最少需要多久。\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cbr\u003e \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:21px;\"\u003e \u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e输入包含多组测试数据。\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e对于每组测试数据:\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e第\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e1\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e行,包含三个整数\u003c/span\u003e\u003cspan\u003e\u003cspan style\u003d\"font-size:14px;\"\u003en, m, r (2 ≤ n ≤ 50, 1 ≤ m ≤ 50, 1 ≤ r ≤ 10\u003c/span\u003e\u003csup\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e5\u003c/span\u003e\u003c/sup\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e)\u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e。\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e接下来包含\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003em\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e个\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003en * n\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e的矩阵,每个元素是在\u003c/span\u003e\u003cspan\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e[0, 10\u003c/span\u003e\u003csup\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e6\u003c/span\u003e\u003c/sup\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e]\u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e内整数。\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e第\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e个矩阵中第\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ej\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e行第\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ek\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e列表示第\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e种汽车通过城市\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ej\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e向城市\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ek\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e的道路所需要的时间,输入数据保证对角线都是\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e0\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e。\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e接下来\u003c/span\u003e\u003cspan style\u003d\"font-size:14px;\"\u003er\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e行中,每行包含三个整数\u003c/span\u003e\u003cspan\u003e\u003cspan style\u003d\"font-size:14px;\"\u003es\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e, t\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e, k\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e (1 ≤ s\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e, t\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e ≤ n, s\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e !\u003d t\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e, 0 ≤ k\u003c/span\u003e\u003csub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003ei\u003c/span\u003e\u003c/sub\u003e\u003cspan style\u003d\"font-size:14px;\"\u003e ≤ 1000)\u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e,表示每回合的起点,终点,更换汽车次数的限制。\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-size:14px;\"\u003e\u0026nbsp;\u003c/span\u003e \u003c/p\u003e \u003cp style\u003d\"text-indent:24.0pt;\"\u003e \u003cspan style\u003d\"font-family:宋体;font-size:14px;\"\u003e处理到文件结束\u003c/span\u003e\u003cspan\u003e\u003c/span\u003e \u003c/p\u003e \u003cspan\u003e\u003c/span\u003e \u003cp\u003e \u003cbr\u003e \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan style\u003d\"font-size:14px;\"\u003e对于每组测试数据:\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;\"\u003e请对应每回合输出完成该回合所需要的最少时间。\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cbr\u003e \u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e4\u0026nbsp;2\u0026nbsp;3\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e0\u0026nbsp;1\u0026nbsp;5\u0026nbsp;6\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e2\u0026nbsp;0\u0026nbsp;3\u0026nbsp;6\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e1\u0026nbsp;3\u0026nbsp;0\u0026nbsp;1\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e6\u0026nbsp;6\u0026nbsp;7\u0026nbsp;0\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e0\u0026nbsp;3\u0026nbsp;5\u0026nbsp;6\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e2\u0026nbsp;0\u0026nbsp;1\u0026nbsp;6\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e1\u0026nbsp;3\u0026nbsp;0\u0026nbsp;2\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e6\u0026nbsp;6\u0026nbsp;7\u0026nbsp;0\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e1\u0026nbsp;4\u0026nbsp;2\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e1\u0026nbsp;4\u0026nbsp;1\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-size:14px;line-height:1;\"\u003e1\u0026nbsp;4\u0026nbsp;3\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cbr\u003e \u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan style\u003d\"font-family:Consolas;font-size:14px;line-height:1;\"\u003e3\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-family:Consolas;font-size:14px;line-height:1;\"\u003e4\u003c/span\u003e \u003c/p\u003e \u003cp\u003e \u003cspan style\u003d\"font-family:Consolas;font-size:14px;line-height:1;\"\u003e3\u003c/span\u003e \u003c/p\u003e"}}]}