{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cspan style\u003d\"line-height:1.5;\"\u003eN个城市之间需要架设通信网络。网络线必须沿着城市之间的公路架设,但对于每条公路,可以有多种不同的铺线方案;通信质量较好的方案所需花费的成本也比较高。你的任务是设计一个通信网络,选择合适的铺线方案,使得在通信质量有保障的前提下,总成本最低。具体而言,n个城市可以看作是一个无向图G中的节点,城市之间的公路可以看作是G中的无向边。对于G的每条边e,都有一个表\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e Le\u003d(d1,c1),(d2,c2),...,(dk,ck)\u0026nbsp;\n\u003cbr\u003e 其中d1\u0026gt;d2\u0026gt;...\u0026gt;dk,且c1为了简化问题,题中所给定的G是一棵树。对于这棵树的每条边,你需要选择恰当的铺线方案,使得任意两个城市之间的网络延时都不超过t(一条路径上的网络延时是这条路径上所有边的网络延时之和)。\u0026nbsp;\n\u003cbr\u003e 请编写程序构造一个满足条件的通信网络,使得总成本最低。\u0026nbsp;\n\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan\u003e输入文件的第一行是二个正整数n,t,分别表示图G的节点数和通信网络中任意两个节点之间所允许的最大延时,其中2≤n≤100,节点依次编号为1,2,...,n。接下来的n-1行,每行表示一条边的信息。第i行的形式如下:\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e \n\u003cspan\u003exi yi ki d1 c1 d2 c2 ... dki cki\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e \n\u003cspan\u003e其中1≤xi,yi≤n,d1\u0026gt;d2\u0026gt;...\u0026gt;dki且c1\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cspan\u003e输出文件只包含一个数字,即构造满足条件的通信网络最低成本。如果无解,输出-1。\u0026nbsp;\u003c/span\u003e\n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3 20\r\n1 2 2 10 5 7 6\r\n2 3 2 14 2 10 4\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eSample Output\u003c/h2\u003e\n\u003cpre class\u003dcontent\u003e\u003cspan class\u003dsampledata\u003e9\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e9\u003c/span\u003e\u003c/pre\u003e\u003ch2\u003eHINT\u003c/h2\u003e\n\u003cdiv class\u003dcontent\u003e\u003cp\u003e\u003c/p\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}