网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NOIP2010冲刺十三]逃离遗迹
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | escapeb.in | 输出文件 | escapeb.out |
【题目描述】
根据外星人的回信,在遗迹分布着三样道具。当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-l条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A,B,C的房间内拿到道具,并且准备撤退。由于只有一架直升机,所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上,能够使三人到达该房间的距离之和最短。
【输入格式】
第1行:四个整数N、A、B、C。
第2..N行:每行三个整数u,v,w,表示存在连接房间u,v的通道,长度w。【输出格式】
第1行:一个整数,表示汇合房间的编号。若存在多个解,输出字典序最小的。
第2行:一个整数,表示三人到该房间距离之和。
【样例输入】
5 3 1 4 3 5 5 4 3 9 4 1 7 1 2 1
【样例输出】
4 16
【提示】
对于50%的数据:1≤N≤1,000。
对于100%的数据:1≤N≤20,000。 1≤A,B,C,u,v<=N且A,B,C不相等;u,v不相等。 1≤w≤1,000。