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