spfa求最短路 – 算法板子leetcode刷题题解

#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int he[N], w[N], e[N], ne[N]; int idx, n, m; int d[N]; bool st[N]; queue<int> q; void add(int x, int y, int z) {     w[idx] = z;     e[idx] = y;     ne[idx] = he[x];     he[x] = idx++; } int spfa() {     memset(d, 0x3f, sizeof d);     d[1] = 0;     st[1] = true;     q.push(1);     while (q.size()) {         int t = q.front();         q.pop();         st[t] = false;         for (int i = he[t]; i != -1; i = ne[i]) {             int j = e[i];             if (d[j] > d[t] + w[i]) {                 d[j] = d[t] + w[i];                 if (!st[j]) {                     st[j] = true;                     q.push(j);                 }             }         }     }     if (d[n] == 0x3f3f3f3f) return -1;     else return d[n]; } int main() {     memset(he, -1, sizeof he);     cin >> n >> m;     for (int i = 0; i < m; ++i) {         int x, y, z;         cin >> x >> y >> z;         add(x, y, z);     }     int r = spfa();     if (r == -1) cout << "impossible" << endl;     else cout << r << endl;     return 0; }

spfa求最短路 – 算法板子leetcode刷题题解部分资料来自网络，侵权毕设源码联系删除