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

读完题很简单可以发现这是一个最短路径问题，由于m^2<n，所以这是一个稀疏图，适合用小根堆优化的dijkstra算法代码如下

#include <bits/stdc++.h>
using namespace std;
constexpr int N=200005; //最大点的数量
constexpr int M=200005; //最大边数，由于双向边后续会*2，避免越界
vector<int>head(N,0);
vector<int>Next(M*2,0);
vector<int>to(M*2,0);
vector<int>weight(M*2,0); 
int cnt=1;
void add(int u,int v,int w) {
    Next[cnt]=head[u];
    to[cnt]=v;
    weight[cnt]=w;
    head[u]=cnt++;
}
//以上均为链式前向星建图，不必多说
int dijkstra(int start,int end,int n) {
    vector<int>dis(n+1,INT_MAX);	//dj数组
    vector<bool>visited(n+1,false); //判断是否访问过数组，防止一个点重复入堆
    dis[start]=0;
    visited[start]=true;
  //起始点的初始化操作
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    for (int i=head[start];i>0;i=Next[i]) {
        dis[to[i]]=weight[i];	//遍历起始点可以去的每一个点初始化dj数组的值
        if (!visited[to[i]]) {
            pq.emplace(weight[i],to[i]); //这里dis[to[i]]也可以，初始化我们的堆
          //first为点到点的当前最小距离，second为点的编号
        }
    }
    while (!pq.empty()) {	//非空表达，如果空了就代表每条边都加完了
        auto x=pq.top();	//取堆顶起始点到该点的最短距离的点
        pq.pop();
        if (x.first==INT_MAX) {
            break;	//小根堆堆顶如果是INT_MAX代表已经没有可以到达的点
        }
        if (visited[x.second]) {
            continue;	//如果该点入堆过则直接跳过
        }
        visited[x.second]=true; //访问过的点标记
        for (int i=head[x.second];i>0;i=Next[i]) {	//访问该点可以到达的所有点，查看是否可以让dj数组的值变小
            if (x.first+weight[i] < dis[to[i]]) {
                dis[to[i]]=x.first+weight[i];	//可以更小就更新
                pq.emplace(dis[to[i]],to[i]);	//新的距离按该顺序入堆
            }
        }
    }
    return dis[end]; //最终dj数组的值下标为点的编号，数组中对应的值为起始点到该点的最小距离
}
int main() {
    int n,m;cin >> n >> m;
    for (int i=0;i<m;i++) {	//如题意，建图
        int u,v,w;cin >> u >> v >> w;
        add(u,v,w);
        add(v,u,w); //双向边别忘了哦
    }
    if (dijkstra(1,n,n)==INT_MAX) {
        cout<<"qwb baka"<<endl;
    }
    else {
        cout<<dijkstra(1,n,n)<<endl;
    }
}