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

#include<bits/stdc++.h> using namespace std; #define ll long long #define sz(x) (int)x.size() #define lf(i,a,b) for(int i=a;i<=b;i++) #define rf(i,b,a) for(int i=b;i>=a;i--) #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second #define ct const int #define cl const ll #define all(x) x.begin(),x.end() #define pb push_back #define po pop_back #define qp emplace #define eb emplace_back #define vt vector #define vl vector #define vb vector #define vvl vector<vector> #define vvt vector<vector> #define vvb vector<vector> #define vp vector #define vvp vector<vector> #define md2(n,m,val) vvl(n, vector(m, val)) #define mb2(n,m,val) vvb(n, vector(m, val)) #define md1(n,val) vl(n,val) #define mb1(n,val) vb(n,val) #define mxhead(T) priority_queue<T,vector> #define mnhead(T) priority_queue<T,vector,greater> #define E exp(1.0) const int N = 5005; const int INF = 0x3f3f3f3f; vector g[N]; int d[N]; bool vis[N];

void dij(int s) { mnhead(pii) q;

memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));

d[s] = 0;
q.qp(0, s);

while (!q.empty()) {
    auto [dis, u] = q.top(); q.pop();
    if (vis[u]) continue;
    vis[u] = 1;

    for (auto [v, w] : g[u]) {
        if (d[v] > d[u] + w) {
            d[v] = d[u] + w;
            q.qp(d[v], v);
        }
    }
}

}

void solve() { int n, m; cin >> n >> m;

// 清空静态图
for (int i = 1; i <= n; i++) g[i].clear();

while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].eb(v, w);
    g[v].eb(u, w);
}

dij(1);
cout << (d[n] == INF ? -1 : d[n]) << endl;

}

int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }