问题 1080. -- 【基础图论】有向图的单源点最短路径

1080: 【基础图论】有向图的单源点最短路径

时间限制: 1 Sec  内存限制: 64 MB
提交: 46  解决: 19
[提交][状态][讨论版]

题目描述

给定有向无权图,求指定源点S到目标点T的最短路径(路径长度定义为从S到T经过的边的条数)。

输入

第1行:2个空格分开的整数n(2≤n≤200)和m(10≤m≤20000),分别表示图的顶点数和边数。

第2..m+1行:每行2个空格分开的整数i,j,i表示一条边的起点,j表示终点。

第m+2行:2个整数S, T。S表示源点,T表示目标点。

输出

第1行:1个整数,表示从S到T的最短路径的长度。如果从S到T没有路径,输出"no solution"。如果存在路径,则输出第2行,否则无第2行。

第2行:1个顶点序列,表示从s到t的最短路径。每2个顶点之间用1个空格分开。如果S==T,则只输出一个点。

如果有多组解,输出字典序最小的解。

样例输入

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

样例输出

3
3 5 4 2

提示

来源

[提交][状态]