OpenJudge

E01P03:带权最短路

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

给定带权无向图G(V,E)和源点s/终点t,求一条 s->t 的最短路径。假设读入边的列表是有(字典)序的(既邻接表就是有序的)。

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