2018年长沙理工大学第十三届程序设计竞赛 E 小木乃伊到我家

题目描述

AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能走到AA家），快递姐姐
找上聪明的ACMer，想请你帮忙找出最快到达AA家的路，你行吗？

输入描述:

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，AA所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，w<=100000），分别表示城市u和城市v之间有一条长为w的路。

输出描述:

输出结果占一行，输出快递姐姐到达AA家最短需要走多远的路，如果没有路能走到AA家，则输出“qwb baka”（不用输出双引号）。

示例1

输入

复制

输出

复制

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <queue>
 9 #include <set> 
10 #include <map>
11 using namespace std;
12 #define  pi acos(-1.0)
13 #define ll long long 
14 #define P pair<ll,ll>
15 #define pu push_back
16 const ll inf = 1e12+100;
17 const int N =2e5+100;
18 int n,m;
19 ll  u,v,w,cnt;
20 struct Edge{
21     ll fr,to,val,nex;
22     Edge(){}
23     Edge(ll fr,ll to,ll val,ll nex):fr(fr),to(to),val(val),nex(nex){}
24 }e[N*2];
25 vector<Edge>ve[N*2];
26 ll d[N],head[N];
27 void add(ll u,ll v,ll w){
28     e[cnt].fr=u;
29     e[cnt].to=v;
30     e[cnt].val=w;
31     e[cnt].nex=head[u];
32     head[u]=cnt++;
33 }
34 void bfs()//数据量较大的单源最短路径。     
35 {
36     priority_queue<P,vector<P>,greater<P> >Q;//按pair的first排序 top最小 
37     ll x=0,y=1;
38     d[y]=x;
39     Q.push(P(x,y));//pair表示1到P.second的距离为P.first
40     while(!Q.empty()){
41         P tmp =Q.top();
42         Q.pop();
43         ll v= tmp.second;
44         if(d[v]<tmp.first ) continue;//那么，走这条路的距离会大 
45         for(int i=head[v];i!=-1;i=e[i].nex){
46             Edge ee = e[i];//Edge 表示v到ee.to的距离为ee.w
47             ll t= ee.to;
48             ll ww = ee.val;
49             if(d[t]>d[v]+ww){
50                     d[t]=d[v]+ww;
51                 Q.push(P(d[t],t));
52             }
53         }
54     }
55 }
56 int main()
57 {
58     scanf("%d%d",&n,&m);
59     for(int i=0;i<N;i++) d[i] = inf,head[i]=-1;
60     cnt=0;
61     for(int i=0;i<m;i++){
62         scanf("%lld%lld%lld",&u,&v,&w);
63         add(u,v,w),add(v,u,w); 
64     } 
65     bfs();
66     if(d[n]!=inf)  printf("%lld
",d[n]);
67     else{
68         printf("qwb baka
");
69     }
70     return 0;
71 }
72     
73