做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2263. -- 下一步去哪儿

2263: 下一步去哪儿

时间限制: 1 Sec  内存限制: 128 MB
提交: 75  解决: 26
[上一题][提交][讨论版][状态][下一题]

题目描述

某国有n个旅游景点,编号分别是1到n。景点之间,有直接相连、间接相连和不相连三种关系。如果景点A和景点B直接相连,那么A下一步就可以到达B,B下一步可以到达A。如果景点间接相连,则需要某些景点进行中转。不相连的景点,不能去其他景点,也不能达到。现有各个景点之间的相连情况,现你在第K个景点,请问下一步你可以去哪儿?

输入

第一行:输入三个整数,分别是景点数n、直接相连的数量m和你可能在的景点编号的数量k

接下来m行,每行3个整数u,v,w,表示u和v直接相连,需要花费w的时间

最后一行:k个数,表示你可能在的景点

输出

每个可能在的景点各输出一行,共k行,每一行内容如下:
第一个数是最短时间可以到达的景点,如果时间相同,输出景点编号小的;接下来x个数,分别是下一步可以到达的景点,消息新(靠后的)的先输出。每一行各个数之间用一个空格分开。如果下一步没有景点可以到达,输出0。
什么是靠后的?消息新的?例如,共有5行直接相连的信息,第4行信息比第3行信息要新。

样例输入

10 7 5
1 2 3
1 4 5
1 2 8
2 5 2
2 4 5
2 9 3
2 8 2
1 2 9 4 3

样例输出

2 2 4
5 8 9 4 5 1
2 2
1 2 1
0

提示

5 <= n < 10000
5 <= m < 100000
1 <= k,u,v <= n
1 <= w < 1000

标签

[上一题][提交][讨论版][状态][下一题]