问题 H: 小P上考场

问题 H: 小P上考场

时间限制: 1 Sec  内存限制: 128 MB
提交: 235  解决: 61
[提交] [状态] [讨论版] [命题人:]
题目描述
小P一觉醒来发现天已经亮了。今天是程序设计大赛的日子,小P需要尽快赶往考场。 小P家在a号路口,他会告诉你哪些路口是相联通的,距离是多少。赛场在b号路口,该市道路没有单行道。 小P想让你帮他规划到考场的路线,他希望找到这条最短的路线以用最短时间抵达考场。
输入
第一行四个整数n,m,a,b (1<=n<=2500 ,1<=m<=6200 ,1<=a,b<=n ) ,n表示有n个路口,m表示有m条路,每两个路口之间连通算一条路,接下来m行,每行三个数,x,y,c代表x路口到y路口之间有一条路距离为c 
输出
一个数,小P家到比赛现场的距离。
样例输入 Copy
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
样例输出 Copy
7
提示

1<=n<=2500

1<=m<=6200

1<=a,b<=n