{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\n\u003cp\u003e\n在魔法之地,每个春天都会举行一次年度游行。\n\u003cbr\u003e\n\u003cbr\u003e\n魔法之地有\u003cb\u003eN\u003c/b\u003e个城市,城市之间有\u003cb\u003eM\u003c/b\u003e条有向道路。\n\u003cbr\u003e\n在游行中,会有一些(可能为0)英雄在这片土地上旅行,每个英雄:\n他从城市begin[i]出发,旅行到一些城市,然后结束在城市end[i]。请注意:begin[i]可能等于end[i],但他在旅行过程中必须至少移动到另一个城市。他可以多次走同一条路,但每次都会有一定的费用。\n\u003cbr\u003e\n\u003cbr\u003e\n这次游行的费用是以下几项的总和:\n\u003cbr\u003e\n1. 在道路上旅行的费用总和。(如果一条路被k个英雄经过,那么必须计算k次。)\n\u003cbr\u003e\n2. 如果对于一个英雄,他结束在一个不等于他的起始城市,即begin[i] !\u003d end[i],那么将他送回家将花费\u003cb\u003eC\u003c/b\u003e美元。\n\u003cbr\u003e\n3. 如果对于一个城市,没有英雄访问,那么我们必须支付\u003cb\u003eC\u003c/b\u003e美元给市民作为补偿。\n\u003cbr\u003e\n\u003cbr\u003e\n\u003cb\u003eC\u003c/b\u003e的值可能每年都会变化,我们可以预测接下来\u003cb\u003eK\u003c/b\u003e年的这个值。\n你的任务是:计算每年的最小费用。\n\u003cbr\u003e\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e\n在第一行,有3个整数:\u003cb\u003eN\u003c/b\u003e,\u003cb\u003eM\u003c/b\u003e和\u003cb\u003eK\u003c/b\u003e。\n\u003cbr\u003e\n在接下来的\u003cb\u003eM\u003c/b\u003e行里:\n\u003cbr\u003e\n有3个整数:\u003cb\u003eS[i]\u003c/b\u003e,\u003cb\u003eT[i]\u003c/b\u003e,和\u003cb\u003eV[i]\u003c/b\u003e,描述了一条从\u003cb\u003eS[i]\u003c/b\u003e到\u003cb\u003eT[i]\u003c/b\u003e的有向道路,费用为\u003cb\u003eV[i]\u003c/b\u003e美元。\n\u003cbr\u003e\n在接下来的\u003cb\u003eK\u003c/b\u003e行里:\n有一个整数:\u003cb\u003eC[i]\u003c/b\u003e,描述了那一年\u003cb\u003eC\u003c/b\u003e的值。\n\u003cbr\u003e\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e\n输出\u003cb\u003eK\u003c/b\u003e行:\n每行包含一个整数,对应每年的最小费用。\n\u003ch3\u003e约束\u003c/h3\u003e\n2 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 250\n\u003cbr\u003e\n1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 30000\n\u003cbr\u003e\n1 \u003c\u003d \u003cb\u003eK\u003c/b\u003e \u003c\u003d 10000\n\u003cbr\u003e\n\u003cb\u003eS\u003c/b\u003e[i] !\u003d \u003cb\u003eT\u003c/b\u003e[i], 1 \u003c\u003d \u003cb\u003eS\u003c/b\u003e[i], \u003cb\u003eT\u003c/b\u003e[i] \u003c\u003d \u003cb\u003eN\u003c/b\u003e\n\u003cbr\u003e\n1 \u003c\u003d \u003cb\u003eV\u003c/b\u003e[i] \u003c\u003d 10000\n\u003cbr\u003e\n1 \u003c\u003d \u003cb\u003eC\u003c/b\u003e \u003c\u003d 10000\n\u003cbr\u003e\n注意:某一对城市之间可能有多于1条道路。\n\n\u003ch3\u003e例子\u003c/h3\u003e\n\u003cpre\u003e\r\n\u003cb\u003eInput:\u003c/b\u003e\r\n6 5 3\r\n1 3 2\r\n2 3 2\r\n3 4 2\r\n4 5 2\r\n4 6 2\r\n1\r\n5\r\n10\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n6\r\n21\r\n32\r\n\u003c/pre\u003e\n\u003cbr\u003e\n\u003cb\u003e解释\u003c/b\u003e\n\u003cbr\u003e\n在第一年,由于\u003cb\u003eC\u003c/b\u003e非常小,一个最佳解决方案是:没有英雄旅行,我们为每个城市支付1美元作为补偿。\n\u003cbr\u003e\n在第二年,一个最佳解决方案是:一个英雄在路径:1-\u003e3-\u003e4-\u003e5上旅行。我们为道路支付2+2+2\u003d6美元,为将他送回城市1支付5美元,并为城市2和6支付5美元作为补偿。\n\u003cbr\u003e\n在第三年,一个最佳解决方案是:一个英雄在路径:1-\u003e3-\u003e4-\u003e5上旅行,另一个英雄在路径:2-\u003e3-\u003e4-\u003e6上旅行。"}}]}