没有注释 没有题解 只有代码 spfa

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>

#define int long long
#define PII pair<int, int> 
#define inf 0x3f3f3f3f
#define all(v) v.begin() , v.end()

using namespace std;
const int N = 2e6 + 10;
int e[N] , ne[N] , h[N] , rh[N] , idx , price[N];
bool st[N];
int dmin[N] , dmax[N];
int n , m;

void add(int *h , int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

void spfa(int *dist , int *h , int start , bool flag)
{
    if (flag) memset(dist , 0x3f , sizeof dmin);

    memset(st , false , sizeof st);
    dist[start] = price[start];
    st[start] = true;
    queue<int> q;
    q.push(start);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if (flag && dist[j] > min(dist[t] , price[j]) || !flag && dist[j] < max(dist[t] , price[j]))
            {
                if (flag) dist[j] = min(dist[t] , price[j]);
                else dist[j] = max(dist[t] , price[j]);

                if (!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }            
        }
    }

}

void solve()
{
    int n , m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) cin >> price[i];

    memset(h , -1 , sizeof h) , memset(rh , -1 , sizeof rh);

    for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(h , a , b) , add(rh , b , a);
        if (c == 2) add(h , b , a) , add(rh , a , b);
    }

    spfa(dmin , h , 1 , true);
    spfa(dmax , rh , n , false);

    int ans = 0;
    for (int i = 1 ; i <= n ; i ++ ) ans = max(ans , dmax[i] - dmin[i]);

    cout << ans << endl;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    solve();
    return 0;
}