1298 问题 D: 德克萨斯长角牛

 时间限制: 1s 内存限制: 128MB
题目描述

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

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 < = T < = 2,500)个城镇，方便地标号为1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。考虑这个有7个城镇的地图。城镇5是奶源，城镇4是终点（括号内的数字是道路的通过费用）。

德克萨斯长角牛

经过路线5-6-3-4总共需要花费3 (5-> 6) + 4 (6-> 3) + 3 (3-> 4) = 10的费用。

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

输入

第一行：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
提示
零基础同学可以先学习视频课程，包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程，提供视频讲解以及配套习题，还有老师答疑，点击这里了解课程详情

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油加油
                        

                    

                

                

                    

                        
比赛状况