牛客小白月赛6 I 公交线路最短路模板题-白红宇

牛客小白月赛6 I 公交线路最短路模板题

阅读量：6920 次

发布时间：2019-06-27

本文共 1133 字，大约阅读时间需要 3 分钟。

链接：

来源：牛客网

题目描述

P市有n个公交站，之间连接着m条道路。P市计划新开设一条公交线路，该线路从城市的东站（s点）修建到西站（t点），请为P市设计一条满足上述条件并且最短的公交线路图。

输入描述:

第一行有5个正整数n，m，s，t。 接下来m行，每行3个数a,b,v描述一条无向道路a——b，长度为v。

输出描述:

如果有解，输出一行，表示满足条件的最短公交线路的长度c。 否则，输出“-1”

示例1

输入

3 3 1 21 2 32 3 41 3 5

输出

示例2

输入

3 3 1 21 2 52 3 31 3 1

输出

示例3

输入

3 1 1 11 2 1

输出

备注:

对于100%的测试数据： 1 ≤ s,t ≤ n ≤ 1000 1 ≤ m ≤ 10000 1 ≤ 道路的长度 ≤ 10000 分析：一个裸的最短路模板题 搞不懂搞不懂，比赛的时候为什么没有人过这个题？ 这套题目后面的题都好做，卡在前面真的难受 这榜真的好歪 AC代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 1010using namespace std;vector
            
             
               >E[maxn];int n,m;int d[maxn];void init(){ for(int i=0;i
              
               > n>> m) { int s,t; scanf("%d%d",&s,&t); init(); for(int i=0;i
               
                 >Q; d[s]=0; Q.push(make_pair(-d[s],s));//使得返回最小值，本来是返回最大值 while(!Q.empty()) { int now = Q.top().second; Q.pop(); for(int i=0;i
                
                 d[now]+E[now][i].second) { d[v]=d[now]+E[now][i].second; Q.push(make_pair(-d[v],v)); } } } if(d[t]==1e9) printf("-1\n"); else printf("%d\n",d[t]); } return 0;}