传送门：[NOIP2009]最优贸易 (nowcoder.com)

传送门2：P1073 [NOIP2009 提高组] 最优贸易 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题思路比较多，有分层图论，还可以用Tarjan缩点 + DP，由于俺的水平不够，所以用分层图论吧。

之前也写过一篇分层图论的文章《[JLOI2011]飞行路线（dijkstra分层最短路） – ErikTse Runtime》。

思路分析：

注意题目中说到“一定从1节点开始，N节点离开”。并且每个点的状态有三个，分别是：

• 没买入
• 买入没卖出
• 卖出了

那么考虑将图分成三层，最上层（第一层）代表没买入的点，中间层（第二层）表示买入没卖出的点，最下层（第三层）表示卖出了的点。

每一层分别有N个，可以用一维数组表示。[1,N]表示第一层，[N + 1,N * 2]表示第二层，[N * 2 + 1,N * 3]表示第三层。

不难发现，每一层之间可以自由移动（权值为0），因为同一层之间移动不会发生状态变化，所以权值为0。

边，只能在同一层中或从上层指向下层，因为不可能从买入没卖出的状态进入没买入的状态。

商人只进行一次交易，起点为1，终点为最下层的N，也就是数组中的3 * N，注意商人可能没进行交易，所以要加一条从N到3 * N权值为0的边。

将图建好之后，采用SPFA求一次最长路，因为dijkstra不能求最长路，所以采用已死的SPFA（其实SPFA的效率比Bellman-Ford还好，但是在竞赛界风评不好）。

SPFA的算法具体过程：

• 创建队列queue<int> q
• 创建inq[]数组表示某个点是否在队列中，inq数值随着push和pop变化。
• int d[]表示某个点到起点的最大距离，初始化为-inf
• 当w + d[x] > d[nx]时，更新nx的值，如果nx不在队列中就入队，已在就不管

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
	int s = 0,w = 1;char c = gc();
	while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*--------全局变量--------*/
typedef pair<int, int> PII;
const int maxn = 1e5 + 9,inf = 1e9;
int N, M;
int val[maxn];
struct Edge{int x, w;};
vector<Edge> g[maxn * 3];//分三层 
int d[maxn * 3];
/*--------自定义函数-------*/

void spfa(int s)
{
	for(int i = 1;i <= N * 3; ++ i)d[i] = -inf;
	bitset<maxn * 3> inq;//inq表示在队列中 
	d[s] = 0;
	queue<int> q;inq[s] = 1;q.push(s);
	while(!q.empty())
	{
		int x = q.front();inq[x] = 0;q.pop();
		for(auto [nx, nw] : g[x])
		{
			if(d[x] + nw > d[nx])
			{
				d[nx] = d[x] + nw;
				if(!inq[nx]){inq[nx] = 1;q.push(nx);}
			}
		}
	}
}

signed main()
{
//	freopen("in.txt","r",stdin);
	cin >> N >> M;
	for(int i = 1;i <= N; ++ i)val[i] = readInt();
	int T = 3 * N;
	while(M --)
	{
		int x = readInt(), y = readInt(), op = readInt();
		g[x].pb({y, 0});
		g[x].pb({N + x, -val[x]});
		g[N + x].pb({N + y, 0});
		g[N + x].pb({N * 2 + x, val[x]});
		g[N * 2 + x].pb({N * 2 + y, 0});
		if(op == 2)
		{
			g[y].pb({x, 0});
			g[y].pb({N + y, -val[y]});
			g[N + y].pb({N + x, 0});
			g[N + y].pb({N * 2 + y, val[x]});
			g[N * 2 + y].pb({N * 2 + x, 0});
		}
	}
	g[N].pb({T, 0});
    spfa(1);
    pr("%lld\n", d[T]);
	return 0;
}