堆优化 迪加斯特拉算法 ```cpp #include <cstdio> #include <vector> #include <queue> #include <tuple> using namespace std; int main() { const int INF = 1e9; int n, m; scanf("%d %d", &n, &m); vector<int> dian(n); vector<vector<tuple<int, int>>> G(n); // [u] -> <v, w> for (int i = 0; i < n; ++i) scanf("%d", &dian[i]); for (int i = 0, u, v, w; i < m; ++i) { scanf("%d %d %d", &u, &v, &w); --u, --v; G[u].push_back(make_tuple(v, w + dian[v])); G[v].push_back(make_tuple(u, w + dian[u])); } // [L, 点] priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> pq; vector<int> dis(n, INF); dis[0] = 0; pq.push(make_tuple(0, 0)); while (pq.size()) { int d, x; tie(d, x) = pq.top(); pq.pop(); if (d > dis[x]) { if (x == n - 1) break; continue; } for (auto& it : G[x]) { int dx = d + get<1>(it); if (dx < dis[get<0>(it)]) { dis[get<0>(it)] = dx; pq.push(make_tuple(dx, get<0>(it))); } } } printf("%d\n", dis[n - 1] - dian[n - 1]); return 0; } ```