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

using namespace std;
const int maxn=200001;
struct E{
    int to,dis;
};
bool operator<(const E a,const E b){
    return a.dis>b.dis;
}
vector<E>G[maxn];
priority_queue<E>q;
int n,m,u,v,w,dis[200001];
int main(){
    cin>>n>>m;
    for(int i=0;i<=n;i++)
        dis[i]=1e9+7;
    dis[1]=0;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    q.push({1,0});
    while(!q.empty()){
        E fro=q.top();
        q.pop();
        for(int i=0;i<G[fro.to].size();i++){
            int to=G[fro.to][i].to,d=G[fro.to][i].dis;
            if(dis[fro.to]+d<dis[to]){
                dis[to]=dis[fro.to]+d;
                q.push({to,dis[to]});
            }
        }
    }
    if(dis[n]==1e9+7)
        cout<<"qwb baka";
    else
        cout<<dis[n];
}