小木乃伊到我家

最短路模板，加一个判断一下最后一步dis[n]与inf关系，若大于等于，那就输出qwb baka就成。

#include <bits/stdc++.h>

using namespace std;

int n,m;
const int maxn=200005;
const int inf=0x3f3f3f3f;
struct node
{
    int v;
    int w;
    node(int v,int w):v(v),w(w){}
    bool operator<(const node & t)const
    {
        return w>t.w;
    }
};

vector<node>dij[maxn];

int vis[maxn];
int dis[maxn];

void dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));

    dis[s]=0;
    priority_queue<node> Q;
    Q.push(node(s,dis[s]));
    while(!Q.empty())
    {
        int u=Q.top().v;  //点 
        Q.pop();
        if(vis[u])
        continue;

        vis[u]=1;

        for(int i=0;i<dij[u].size();i++)
        {
            int v=dij[u][i].v;
            int w=dij[u][i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                Q.push(node(v,dis[v]));
            }
        }
    }
}


int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        dij[u].push_back(node(v,w));
        dij[v].push_back(node(u,w));
    }

    dijkstra(1);
    if(dis[n]>=inf)
    printf("qwb baka\n");
    else
    cout<<dis[n]<<endl;
    return 0;
}

另外一个基本一样的，为了熟悉模板qaq

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=200005;

struct node
{
    int to; //终点 
    int s;  //权值 
};

vector<node> f[maxn];
int dis[maxn];
int vis[maxn];

int n,m;

void dijkstra(int t)
{
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));

    priority_queue<pii,vector<pii>,greater<pii> > q;
    dis[t]=0;
    q.push(pii(0,t));
    while(!q.empty())
    {
        pii x=q.top();
        q.pop();
        int tt=x.second;
        if(vis[tt])
        {
            continue;
        }
        vis[tt]=1;
        for(int i=0;i<f[tt].size();i++)
        {
            node a=f[tt][i];
            if(dis[a.to]>dis[tt]+a.s)
            {
                dis[a.to]=dis[tt]+a.s;
                q.push(pii(dis[a.to],a.to));
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        f[u].push_back({v,w});
        f[v].push_back({u,w});
    }
    dijkstra(1);
    if(dis[n]>=inf)
    {
        cout<<"qwb baka"<<endl;
    }
    else
    {
        cout<<dis[n]<<endl;
    }
    return 0;
}