{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003edd \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background-color: #f5f5f5;\n border: 1px solid #ccc;\n border-radius: 4px;\n}\u003c/style\u003e","sections":[{"title":"Description","value":{"format":"HTML","content":"\u003cdiv\u003eBESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BES\u003c/div\u003e\r\n\u003cdiv\u003eSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 \u0026lt;\u003d M \u0026lt;\u003d 10,000)条路, 每条路连接两个用1..N(1\u003c/div\u003e\r\n\u003cdiv\u003e\u0026nbsp;\u0026lt;\u003d N \u0026lt;\u003d 1000)标号的地点. 更方便的是,如果X\u0026gt;Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1\u003c/div\u003e\r\n\u003cdiv\u003e是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 \u0026lt;\u003d K \u0026lt;\u003d 100)条不\u003c/div\u003e\r\n\u003cdiv\u003e同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经. 请帮助BESSIE找出这K条最短路经的长度.你的程\u003c/div\u003e\r\n\u003cdiv\u003e序需要读入农场的地图, 一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i). 所有(X_i, Y_i, D_i)满足(1 \u0026lt;\u003d\u003c/div\u003e\r\n\u003cdiv\u003e\u0026nbsp;Y_i \u0026lt; X_i; Y_i \u0026lt; X_i \u0026lt;\u003d N, 1 \u0026lt;\u003d D_i \u0026lt;\u003d 1,000,000).\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e* 第1行: 3个数: N, M, 和K\u003c/div\u003e\r\n\u003cdiv\u003e* 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e* 第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.\u003c/div\u003e\r\n\u003cdiv\u003e如果多条路经有同样的长度,请注意将这些长度逐一列出.\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\"vjudge_sample\"\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 8 7\r\n5 4 1\r\n5 3 1\r\n5 2 1\r\n5 1 1\r\n4 3 4\r\n3 1 1\r\n3 2 1\r\n2 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n2\r\n3\r\n6\r\n7\r\n-1\r\n输出解释:\r\n路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),\r\n(5-4-3-2-1).\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003ch3\u003eSource\u003c/h3\u003eGold"}}]}