请选手到 http://acm.xidian.edu.cn/contestrank3.php?cid=1038 核对报名,报名失败或尚未报名的尽快报名!

问题 1159. -- 地铁侠

1159: 地铁侠

时间限制: 2 Sec  内存限制: 128 MB
提交: 56  解决: 17
[提交][状态][讨论版]

题目描述

天国的地铁遭到了冥王哈乙丁的破坏,神圣军团的总司令爱神下令天国的地铁侠们携手542基地对冥王哈乙丁展开了激烈的斗争。天国中的 m 条地铁通道连接了 n 个实验室,如今所有的实验室已经被哈乙丁破坏。如果地铁要在两个实验室之间来往,那么地铁在它们之间经过的实验室必须是完好的。

地铁侠(江湖人称瑾爷)具有维护实验室的和平和安宁的能力,可确保地铁顺利通车。

542基地成员能判断两个实验室是否可以连通,不过现在由于哈乙丁的破坏,导致基地成员的判断能力大大减弱,所以请聪明的你来帮忙。如果你算对了,就有可能被邀请加入542基地组织。你只有 t 个单位时间,每个单位时间只能完成一次维护或判断。

注意:天国的地铁通道是单方向的。

输入

多组数据,请处理到文件结束。

每组数据,第一行包含 3 个整数 n, m, t ,用空格分割。

之后 m 行,每行 3 个整数 u, v, w ,用空格分割,表示实验室 u 到 v 有一条地铁通道,长度为 w 。

之后 t 行,每行表示一个任务:

若为 0 x ,表示地铁侠用“ DJ 光环”维护好了编号为 x 的实验室。

若为 1 u v ,表示你要判断 u 到 v 是否通车。

保证 0<n<=300, 0<m<=100000, 0<t<100000, 0<=u, v<n, 0<w<=10000。

输出

对于输入 0 x ,若实验室已经被维护过,输出 "lab x has been repaired!"(不含引号,下同)。

对于输入 1 u v ,若 u 和 v 中至少有一个没有被维护,输出 "help u v"。若无法在 u, v 之间通车,输出 "no path"。否则输出 u 到 v 的最短路的长度。

样例输入

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

样例输出

lab 0 has been repaired!
4
0
help 0 2
9

提示

来源

[提交][状态][讨论版]