没有注释 没有题解 只有代码 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;
}

建立正反图,枚举每个点为终点,正图算出到这个点最小购入价格,反图算出到这个点最大卖出价格,枚举以每个点为终点两者相减的价格更新最大值

#include<bits/stdc++.h>
// #define int long long //memset数组为0x3f时自觉去掉
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define ULL unsigned long long
#define PIII tuple<int,int,int>
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  100000 + 10,M = 2 * 500000 + 10;

int n,m;
int w[N];
bool vis[N];
int dmin[N],dmax[N];
vector<int> Gmin[M],Gmax[M];
void Spfa(vector<int> G[],int dist[],int type)
{
    queue<int> q;
    if(type == 0)
    {
        memset(dist,0x3f,sizeof dmin);
        q.push(1);
        dist[1] = w[1];
        vis[1] = 1;
    }
    else
    {
        memset(dist,-0x3f,sizeof dmax);
        q.push(n);
        dist[n] = w[n];
        vis[n] = 1;
    }

    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int v : G[u])
        {
            if(type == 0 && min(dist[u],w[v]) < dist[v] || type == 1 && max(dist[u],w[v]) > dist[v])
            {
                if(type == 0) dist[v] = min(dist[u],w[v]);
                else dist[v] = max(dist[u],w[v]);
                if(vis[v]) continue;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> w[i];
    while(m--)
    {
        int x,y,z;
        cin >> x >> y >> z;
        Gmin[x].emplace_back(y);
        Gmax[y].emplace_back(x);
        if(z == 2)
        {
            Gmin[y].emplace_back(x);
            Gmax[x].emplace_back(y);
        }
    }

    Spfa(Gmin,dmin,0);
    Spfa(Gmax,dmax,1);

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

    cout << ans;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2025.02.14 14:40:56
 */