做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2435. -- [C++一本通-图论算法]4.热浪

2435: [C++一本通-图论算法]4.热浪

时间限制: 1 Sec  内存限制: 128 MB
提交: 185  解决: 86
[上一题][提交][讨论版][状态][下一题]

题目描述

        得克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!他们的得克萨斯长角牛吃起来不错,可是他们并不是很擅长生产富含奶油的乳制品。Farmer John此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯州运送大量营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

        Farmer John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点,先一共经过T(1<=T<=2500)个城镇,方便地标号为1到T。除了起点和终点外的每个城镇由两条双向道路连向至少两个其他城镇。每条道路有一个通过费用(包括油费、过路费等)。

        给定一个地图,包含C(1<=C<=6200)条直线连接2个城镇的道路。每条道路由道路的起点Rs、终点Re(1<=Rs<=T;1<=Re<=T)和花费(1<=Ci<=1000)组成。求从起点的城镇Ts(1<=Ts<=T)到终点的城镇Te(1<=Te<=T)最小的总费用。

输入

第1行:4个由空格隔开的整数:T,C,Ts,Te。

第2到C+1行:第i+1行描述第i条道路。有3个由空格隔开的整数:Rs,Re和Ci。

输出

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

样例输入

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

样例输出

7

提示

样例说明:5->6->1->4(3+1+3)

标签

[上一题][提交][讨论版][状态][下一题]