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

链接：https://www.nowcoder.com/acm/contest/96/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

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

输入

输出

5

分析：裸的最短路,最后判断一下有没有解即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 999999999
using namespace std;
int N,M,S,T;
struct Node{
    int s,t,c;
}edge[400050];
int next1[400050],head[400050];
int vis[400050],d[400050];

void spfa()
{
    for(int i=0;i<=N;i++) {d[i]=INF;vis[i]=0;} 
    d[S]=0;vis[S]=1;
    queue<int> q;
    q.push(S);
    while(!q.empty())
    {
        int v=q.front();
        vis[v]=0;q.pop();
        int k=head[v];
        while(k!=-1)
        {
            int i=edge[k].t;
            if(d[i]>d[v]+edge[k].c)
            {
                d[i]=d[v]+edge[k].c;
                if(!vis[i])
                {
                    vis[i]=1;
                    q.push(i);
                }
            }
            k=next1[k];
        }
    }
}

int main()
{
    scanf("%d%d",&N,&M);
    S=1,T=N;
    memset(head,-1,sizeof(head));
    M*=2;
    for(int i=0;i<M;i++)
    {
        scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].c);
        next1[i]=head[edge[i].s];
        head[edge[i].s]=i;
        i++;
        edge[i].s=edge[i-1].t;
        edge[i].t=edge[i-1].s;
        edge[i].c=edge[i-1].c;
        next1[i]=head[edge[i].s];
        head[edge[i].s]=i;
    }
    spfa();
    if(d[T]<INF)
    printf("%d
",d[T]);
    else printf("qwb baka
");
    return 0;
}

View Code