OpenJudge

02:吃货冲食堂

总时间限制:
1000ms
内存限制:
65536kB
描述

    Y佬的学生是一群吃货,还没放学就已经满脑子是吃的了。当然,光会想吃的吃货不是一名合格的吃货,吃货还应该有很高智商,比如得会懂得计算出到达食堂最快的一条路,否则是很难跑得过更吃货的学长学姐的。现在吃货的你把校园里各个路口视为图论中的一个节点,当然作为起点的教室和终点的食堂也各被视为一个节点,总共有N个节点,且这些节点都被你编了上了号(从1至N)。

    吃货的你想以此计算出一条到达食堂的最短路径,输出其长度并把路径经过的节点(包含起点和终点)从头到尾输出来。如果有多条最短路径则只输出最短路的条数及路长即可。


输入
第一行包含两个正整数N和M,N代表节点数,M代表图中的边数。所以接下来有M行,每行有三个正整数a,b,c,表示有一条无向边直接连接了节点a和节点b,边长为c。注意:相邻节点间的边数可能多于1条,如果多于一条,则测试数据保证这些边的长度不同。最后一行包含两个正整数S和E,即起点及终点的编号。注意:数据不保证终点可达(可能你们班主任就堵在路上,亦或通往食堂的路在修),如果终点不可达则输出“jiaowaimai”(不包含双引号)。
输出
输出占1或2行。第一行为两个整数,即最短路的条数及最短路长度,由一个空格隔开。如果最短路的条数为1,则在第二行输出最短路经过的节点(包含起止点)。
样例输入
6 6
1 3 5
1 2 1
3 4 8
2 4 6
4 6 9
4 5 2
1 5
样例输出
1 9
1 2 4 5
提示
样例解释:从1到5的最短路只有1条,路长为9。途径1->2->4->5。


数据范围:60%的数据:1<=N<=500 , 0<=M<=20000
100%的数据:1<=N<=5000 , 0<=M<=500000
全局题号
16577
添加于
2018-01-06
提交次数
111
尝试人数
21
通过人数
14