题解 | #【模板】单源最短路2#

# include<iostream>
# include<vector>
# include<queue>
# include<algorithm>
# include<cstdio>
using namespace std;

const int N = 5000 + 5;
int n, m;
int dist[N]; // 起点到其他每个点的距离
vector<int> g[N], e[N]; 
bool vis[N];
queue<int> q; // 队列控制

void spfa(int s){
    for(int i=1; i<=5000; i++){ // 这里题目写的不清楚，点的数量是固定5000, n表示终点
        dist[i] = (1ll << 31) - 1;
        //cout << dist[i] << " &&&& ";
    }
    dist[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()){
        int x = q.front();
        vis[x] = false;
        q.pop();
        for(int i=0; i<g[x].size();i++){
            int y = g[x][i], w = e[x][i];
            if(dist[x] + w < dist[y]){
                dist[y] = dist[x] + w;
                if(!vis[y]){
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(v);
        g[v].push_back(u);
        e[u].push_back(w);
        e[v].push_back(w);
    }
    spfa(1);
    if(dist[n] == (1ll << 31) - 1){
        cout << -1 << endl;
    }else{
        cout  << dist[n] << endl;
    }
    return 0;
}