Skip to content

11528: 【原1528】小天狼星的访问

题目

题目描述

author: 金耀楠 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1528 ## Description

经过数月的准备,小天狼星,一个被诬陷的杀人犯,准备闯入霍格沃茨见见他的侄子。霍格沃茨的地图呈一颗树状分布。每个房间由若干跳过道通向其他房间。由于小天狼星想尽快找到哈利:

  1. 他会从房间0开始找

  2. 他总是会选择离自己最近的房间找,如果仍有多个房间,从序号最小的开始找。

  3. 如果没找到,则继续选最近的房间深入。

  4. 如果已没有房间可走,则返回到上一个房间,继续选择(往回走也算时间哦)。

  5. 当然,除了往回走,小天狼星是不会去一个房间两次的。

Input Format

第1行:n,p,n表示房间个数,p表示哈利所在的房间。

第2 - n行:s,t,l,表示从房间s到房间t的时间为l(0 <= s < t < n)。

Output Format

1行:找到哈利的时间(开始时间为0)。

Sample Input

5 2
0 1 1
0 2 2
1 3 3
1 4 4

Sample Output

18

Hint

对40%的数据:0 < p <= n < 1000。

对100%的数据:0 < p <= n < 100000。

对100%的数据:0 < l <= 2^31-1。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!