这是参考题解中没有存在过的思路.
题意较长请自行观看。
采用分层图思想（我感觉就是dp+spfa），不过过程中因为不存在拓扑序需要迭代
一种语义化的定义： dis[i][0/1][0/1]
具体来说，第一维表示到了那，第二维和第三维分别表示是否买入和卖出。
综上，即：从城市 1 出发到达城市 i，处于 (a,b) 状态时能获得的「最大收益」。
场景一： 我们现在处于dis[i][0][0]的状态：
选择 1：移动到相邻城市 v，仍保持 “没买没卖”；
选择 2：在 u 市买入水晶球，状态变为 dis[u][1][0]。
场景二：当前状态是 dis[u][1][0]（在 u 市，买了没卖）：
选择 1：移动到相邻城市 v，仍保持 “买了没卖”；
选择 2：在 u 市卖出水晶球，状态变为 dis[u][1][1]。
场景三：当前状态是 dis[u][1][1]（在 u 市，买了也卖了）：
选择：移动到相邻城市 v，仍保持 “买了也卖了”。
code
我们用豆包实现了这个思路，洛谷评测通过
#include <bits/stdc++.h>
using namespace std;const int MAXN = 100005;
const int INF = 0x3f3f3f3f; // 无穷大int n, m;
int price[MAXN]; // 每个城市的水晶球价格
vector<int> adj[MAXN]; // 邻接表存储道路
int dis[MAXN][2][2]; // 核心状态：dis[i][a][b]
bool inqueue[MAXN][2][2]; // SPFA入队标记（三维，对应状态）void spfa() {// 1. 初始化状态：非法状态置-INF，合法状态初始为-INF，起点[1][0][0]=0for (int i = 1; i <= n; ++i) {for (int a = 0; a < 2; ++a) {for (int b = 0; b < 2; ++b) {dis[i][a][b] = -INF;inqueue[i][a][b] = false;}}}dis[1][0][0] = 0; // 起点：未买未卖，收益0// 队列存储三元组 (城市i, 买入状态a, 卖出状态b)queue<tuple<int, int, int>> q;q.emplace(1, 0, 0);inqueue[1][0][0] = true;while (!q.empty()) {auto [u, a, b] = q.front();q.pop();inqueue[u][a][b] = false;// ********** 情况1：当前状态是 [0][0]（未买未卖）**********if (a == 0 && b == 0) {// 子情况1.1：移动到相邻城市v，仍保持[0][0]for (int v : adj[u]) {if (dis[v][0][0] < dis[u][0][0]) { // 最大化收益（此处收益为0）dis[v][0][0] = dis[u][0][0];if (!inqueue[v][0][0]) {q.emplace(v, 0, 0);inqueue[v][0][0] = true;}}}// 子情况1.2：在当前城市u买入，状态变为[1][0]int new_profit = dis[u][0][0] - price[u];if (dis[u][1][0] < new_profit) {dis[u][1][0] = new_profit;if (!inqueue[u][1][0]) {q.emplace(u, 1, 0);inqueue[u][1][0] = true;}}}// ********** 情况2：当前状态是 [1][0]（已买未卖）**********else if (a == 1 && b == 0) {// 子情况2.1：移动到相邻城市v，仍保持[1][0]for (int v : adj[u]) {if (dis[v][1][0] < dis[u][1][0]) {dis[v][1][0] = dis[u][1][0];if (!inqueue[v][1][0]) {q.emplace(v, 1, 0);inqueue[v][1][0] = true;}}}// 子情况2.2：在当前城市u卖出，状态变为[1][1]int new_profit = dis[u][1][0] + price[u];if (dis[u][1][1] < new_profit) {dis[u][1][1] = new_profit;if (!inqueue[u][1][1]) {q.emplace(u, 1, 1);inqueue[u][1][1] = true;}}}// ********** 情况3：当前状态是 [1][1]（已买已卖）**********else if (a == 1 && b == 1) {// 子情况3.1：移动到相邻城市v，仍保持[1][1]（交易完成，收益不变）for (int v : adj[u]) {if (dis[v][1][1] < dis[u][1][1]) {dis[v][1][1] = dis[u][1][1];if (!inqueue[v][1][1]) {q.emplace(v, 1, 1);inqueue[v][1][1] = true;}}}}// 非法状态[0][1]：直接跳过，不处理}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);// 输入：城市数n，道路数mcin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> price[i];}// 输入道路（t=1单向，t=2双向）for (int i = 0; i < m; ++i) {int u, v, t;cin >> u >> v >> t;adj[u].push_back(v);if (t == 2) {adj[v].push_back(u);}}// 执行SPFA更新所有状态spfa();// 最终答案：终点n的[1][1]状态最大收益，若为负则选不交易（收益0）int ans = max(dis[n][1][1], 0);cout << ans << endl;return 0;
}