spfa + 贪心

dmin[i] 1~i买入水晶的最低价格
dmax[i] i~n卖出水晶的最高价格

用最短路算法求出这两个结果

求dmin数组的时候从点1跑到点n就行
但是求dmax数组的时候要从点n跑到点1，所以在建图的时候同时建一个反向图（即和原图完全相反的图），然后从点n开始跑就行

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, w[N], ans;
vector<int> adj[N], radj[N]; // radj 反向图 因为后面还需要从n往前走找出卖出水晶的最高价格
int dmin[N], dmax[N]; // dmin[i] 1~i买入水晶的最低价格 dmax[i] i~n卖出水晶的最高价格
bool vis[N];
void spfa_min()
{
  memset(vis, 0, sizeof vis);
  memset(dmin, 0x3f, sizeof dmin);
  queue<int> q;
  dmin[1] = w[1];
  q.push(1), vis[1] = true;
  while (!q.empty())
  {
    auto u = q.front();
    q.pop(), vis[u] = false;
    for (auto v : adj[u])
    {
      if (dmin[v] > min(dmin[u], w[v]))
      {
        dmin[v] = min(dmin[u], w[v]);
        if (!vis[v])
          q.push(v), vis[v] = true;
      }
    }
  }
}
void spfa_max()
{
  memset(vis, 0, sizeof vis);
  queue<int> q;
  dmax[n] = w[n];
  q.push(n), vis[n] = true;
  while (!q.empty())
  {
    auto u = q.front();
    q.pop(), vis[u] = false;
    for (auto v : radj[u])
    {
      if (dmax[v] < max(dmax[u], w[v]))
      {
        dmax[v] = max(dmax[u], w[v]);
        if (!vis[v])
          q.push(v), vis[v] = true;
      }
    }
  }
}
int main() 
{
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> w[i];
  for (int i = 1, x, y, z; i <= m; i++)
  {
    cin >> x >> y >> z;
    adj[x].push_back(y), radj[y].push_back(x);
    if (z == 2)
      adj[y].push_back(x), radj[x].push_back(y);
  }

  spfa_min();
  spfa_max();

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

  return 0;
}

分层图 + spfa

把原图分成三份，第一层表示没买也没卖，第二层表示进行了买，第三层表示进行了买和卖。
存不同层可以这样子 第i层的第j个点下标表示为 $n \ times (i-1) + j$
所以各个数组都要开3倍
同一层的图间互相连边，因为移动不需要花费，所以同一层的边的边权均为0

考虑不同层之间的连边，可能连边的情况只有两种
从 第一层的点i 转移到 第二层的点i 边权为 $-w[i]$
从 第二层的点i 转移到 第三层的点i 边权为 $w[i]$

最后跑一遍最长路，答案在第三层的n点，即d[3 * n]
因为有负边，所以这里用spfa
代码要注意建边的实现

#include<bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, w[N], ans;
vector<pair<int, int>> adj[N * 3];
int dis[N * 3];
bool vis[N * 3];
void spfa()
{
  for (int i = 1; i <= n * 3; i++)
    dis[i] = INT_MIN;
  dis[1] = 0;
  queue<int> q;
  q.push(1), vis[1] = true;
  while (!q.empty())
  {
    auto u = q.front();
    q.pop(), vis[u] = false;
    for (auto [v, w] : adj[u])
    {
      if (dis[v] < dis[u] + w) 
      {
        dis[v] = dis[u] + w;
        if (!vis[v])
          q.push(v), vis[v] = true;
      }
    }
  }
}
int main() 
{
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) 
  {
    cin >> w[i];
    adj[i].push_back({i + n, -w[i]}); // 从第一层的点i转移到第二层的点i 边权为-w[i]
    adj[i + n].push_back({i + 2 * n, w[i]}); // 从第二层的点i转移到第三层的点i 边权为-w[i]
  }
  for (int i = 1, x, y, z; i <= m; i++)
  {
    cin >> x >> y >> z;
    adj[x].push_back({y, 0});
    adj[x + n].push_back({y + n, 0});
    adj[x + 2 * n].push_back({y + 2 * n, 0});
    if (z == 2)
    {
      adj[y].push_back({x, 0});
      adj[y + n].push_back({x + n, 0});
      adj[y + 2 * n].push_back({x + 2 * n, 0});
    }
  }

  spfa();

  cout << dis[n * 3];
  return 0;
}