OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1268--单源最短路径问题

1268: 单源最短路径问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 346  解决: 271
[提交] [状态] [讨论版] [命题人:]

题目描述

给你一个n(1<=n<=2500)个点m(1<=m<=6200)条边的无向图，求s到t的最短路

输入

第一行四个由空格隔开的整数n,m,s,t
之后的m行，每行三个正整数u,v,w(1<=w<=1e9),表示一条从u到v长度为w的边

输出

一个整数表示从s到t的最短路长度。数据保证至少存在一条道路

样例输入 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

来源/分类

分支限界法 
[提交] [状态]