链接：https://www.nowcoder.com/acm/contest/96/E
来源：牛客网
小木乃伊到我家
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能走到AA家），快递姐姐
找上聪明的ACMer，想请你帮忙找出最快到达AA家的路，你行吗？
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”（不用输出双引号）。
输入例子:
4 4
1 2 1
2 3 2
3 4 3
2 3 1
输出例子:
5
-->
示例1
输入
4 4
1 2 1
2 3 2
3 4 3
2 3 1
输出
5
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
const int maxn=;
ll head[maxn*],d[maxn],tol=,n,m;
bool is[maxn];
queue<long long>P;
struct node
{
ll to,next,cost;
}rode[maxn*];
void add(ll a,ll b,ll c)
{
rode[tol].to=b;
rode[tol].cost=c;
rode[tol].next=head[a];
head[a]=tol++;
}
void spfa()
{
for(int i=;i<maxn;i++)d[i]=1e18;
d[]=;is[]=;P.push();
while(!P.empty())
{
ll v=P.front();P.pop();
is[v]=;
for(ll i=head[v];i!=-;i=rode[i].next)
{
node e=rode[i];
if(d[e.to]>d[v]+e.cost)
{
d[e.to]=d[v]+e.cost;
if(!is[e.to])
{
is[e.to]=;
P.push(e.to);
}
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
memset(head,-,sizeof(head));
for(int i=;i<m;i++)
{
ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
spfa();
if(d[n]<1e18/)printf("%lld\n",d[n]);
else printf("qwb baka\n");
return ;
}