营救皮卡丘
提交数: 13, 通过率: 38.46%, 平均分: 46.15
题目描述:
输入格式:
第一行包含三个正整数N,M,K。表示一共有N+1个据点,分别从0到N编号,以及M条无向边。一开始小智一行共K个人均位于0号点。
接下来M行,每行三个非负整数,第i行的整数为Ai,Bi,Li。表示存在一条从Ai号据点到Bi号据点的长度为Li的道路。
输出格式:
仅包含一个整数S,为营救皮卡丘所需要经过的最小的道路总和。
样例输入:
3 4 2 0 1 1 1 2 1 2 3 100 0 3 1
样例输出:
3
提示:
【样例说明】
小智和小霞一起前去营救皮卡丘。在最优方案中,小智先从真新镇前往1号点,接着前往2号据点。当小智成功摧毁2号据点之后,小霞从真新镇出发直接前往3号据点,救出皮卡丘。
【数据规模】
对于10%的数据满足 K = 1,且N = 3,小智将独自前去营救皮卡丘;
对于20%的数据满足 K ≤ 3,且N ≤ 20,被小智单挑剿灭的火箭队加强了防御,增加了据点数;
对于40%的数据满足 K ≤ 3,且N ≤ 100,面对加强的防御,小智拉来了好朋友小霞和小刚,一同前去营救;
对于另外20%的数据满足任意一对据点之间均存在道路,并且对任意的0 ≤ X,Y,Z ≤ N,有不等式L(X,Z) ≤ L(X,Y) + L(Y,Z)成立;
对于100%的数据满足N ≤ 150, M ≤ 20 000, 1 ≤ K ≤ 10, Li ≤ 10 000, 保证小智一行一定能够救出皮卡丘。
至于为什么K ≤ 10,你可以认为最终在小智的号召下,小智,小霞,小刚,小建,小遥,小胜,小光,艾莉丝,天桐,还有去日本旅游的黑猫警长,一同前去大战火箭队。
时间限制: 1000ms空间限制: 256MB
来源: 浙江省选2011day2t2