RT，看前面的帖子应该是出问题的数据一样

但是没想出来怎么改进，下面的回复没看懂。从 $n$ 开始的 dfs 可以设 vis，但是从 $1$ 开始的 dfs 有记录每个点到 $1$ 的所有路径上的最小买入价值，那这样不就必须每个点都 dfs 到底吗

或者说可以改成用拓扑序每个点只遍历一次？但是怎么解决从 $1$ 开始的限制啊

码风良好有注释

// Problem: P1073 [NOIP2009 提高组] 最优贸易
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1073
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define M 100005
const int inf=1e9+7;
int n,m,U,V,o,cntp,ctp,ans,tf,t,vi[M];
int vis[M],fns[M],a[M],Buy[M];//Buy 为某个点到1的路径上的最小值
int sel[M],buy[M],in[M],frp[M];//sel是每个qltfl的最大值,buy是每个qltfl的最小值
//in是入度,frp是每个点来自哪个qltfl
vector<int>road[M],road2[M],rdd[M],rd[M],frd[M];
//road原图 road2反图 rdd每个连通分量的点集
//rd是新图,frd是新图的反图
map<pair<int,int>,int>app;//app[u,v]=1表示有一条u到v的边
queue<int>q;//拓扑用,代码里没用到
void dfs1(int x)//Kosaraju求qltfl,以下简称Ko,问题不在这里
{
	vis[x]=1;
	for(int i=0;i<road[x].size();i++)
	  if(!vis[road[x][i]])
	    dfs1(road[x][i]);
	fns[++cntp]=x;
}
void dfs2(int x)//Ko
{
	buy[cntp]=min(buy[cntp],a[x]);
	sel[cntp]=max(sel[cntp],a[x]);
	frp[x]=cntp,rdd[cntp].push_back(x);
	for(int i=0;i<road2[x].size();i++)
	  if(!frp[road2[x][i]])
	    dfs2(road2[x][i]);
}
void dfs(int x)//出问题的dfs,即从1开始遍历,同时记录路径中的最小值
{
	vi[x]=1;
	for(int i=0;i<rd[x].size();i++)
	{
		Buy[rd[x][i]]=min(Buy[rd[x][i]],min(buy[rd[x][i]],Buy[x]));
		dfs(rd[x][i]);
	}
}
void Dfs(int x)//从n开始遍历反图,这个很好改,问题也不在这里
{
	if(vi[x]) ans=max(ans,sel[x]-Buy[x]);
	for(int i=0;i<frd[x].size();i++)
	  Dfs(frd[x][i]);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>U>>V>>o,road[U].push_back(V),road2[V].push_back(U),(o==2?(road[V].push_back(U),road2[U].push_back(V)):road[0].push_back(0)); road[0].clear();
	for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i); cntp=0; //Ko-1
	for(int i=n;i>=1;i--) if(!frp[fns[i]]) ++cntp,buy[cntp]=inf,sel[cntp]=-inf,dfs2(fns[i]); //Ko-2
	for(int i=1;i<=cntp;i++) {//建立新图
		for(int cc=0,j;cc<rdd[i].size();cc++) {
			j=rdd[i][cc];
			for(int dx=0;dx<road[j].size();dx++) {
				if(!app[make_pair(i,frp[road[j][dx]])]&&i!=frp[road[j][dx]])
				{
					app[make_pair(i,frp[road[j][dx]])]=1;
					frd[frp[road[j][dx]]].push_back(i);
					rd[i].push_back(frp[road[j][dx]]);
					in[frp[road[j][dx]]]++;
				} 
			}
		}
	}
	for(int i=1;i<=cntp;i++) Buy[i]=inf;//初始化
	Buy[frp[1]]=buy[1],dfs(frp[1]),Dfs(frp[n]);//出问题的一行
	cout<<ans<<endl;//输出答案
	return 0;
}