题解 | #小木乃伊到我家#

思路

写一个Dijkstra堆优化的模板供大家参考一下。
（码风比较丑，不要介意）

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,maxm=500005;

struct E{
    int next,to,dis;
}edge[maxm];

struct X{
    int node,dis;
};

int n,m,u,v,w;
int cnt=0,head[maxn],dis[maxn];

bool operator <(const X a,const X b){
    return a.dis>b.dis;
}

inline void addedge(int from,int to,int dis){
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

priority_queue<X>q;

void dijkstra(){
    q.push((X){1,0});
    while(!q.empty()){
        X fro=q.top();
        q.pop();
        for(int i=head[fro.node];i;i=edge[i].next){
            int to=edge[i].to,d=edge[i].dis;
            if(dis[fro.node]+d<dis[to]){
                dis[to]=dis[fro.node]+d;
                q.push((X){to,dis[to]});
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) dis[i]=1e9+7;
    dis[1]=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dijkstra();
    if(dis[n]==1e9+7) cout<<"qwb baka";
    else cout<<dis[n];
    return 0;
}