OpenJudge

E01P02:无权最短路

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

给定无权无向图G(V,E)和源点s/终点t,求 s->t 的最短路径。

假设读入边的列表是有(字典)序的(既邻接表就是有序的)。

输入
第一行包含4个整数N、M、s、t,表示该图共有N个结点和M条无向边。(N <= 5000,M <= 200000)。起点为s,终点为t
接下来M行,每行包含2个整数{u,v},表示有一条无向边连接结点u、v
输出
输出最短路的长度(边数)
若无法到达,输出"No path"
样例输入
4 3 1 4
1 2
1 3
2 4
样例输出
2
全局题号
15258
添加于
2017-07-28
提交次数
54
尝试人数
21
通过人数
21