搜索

分别计算$i$前面的点的最小值和往后的最大值，我们可以使用搜索来处理，这样我们后面枚举的时候，用$O(n)$,就可以了，不用每次都搜索整个图。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> g[N],ng[N];
int w[N],mins[N],maxs[N];
int n,m;
void dfs_min(int u,int m) //找到从1....u的最小值
{
	if(m>=mins[u]) return ; //当前路径一定不可能更新答案
	//可能是前面的路径的值和当前值的最小值
	m=min(m,w[u]);
	mins[u]=m;
	for(int i=0;i<g[u].size();i++)
	{
		dfs_min(g[u][i],m);
	}
}
void dfs_max(int u,int m) //同理找到n...u的最大值
{
    if(m<=maxs[u]) return ;
    m=max(m,w[u]);
    maxs[u]=m;
    for(auto x:ng[u])
    {
        dfs_max(x,m);
    }
}
int main()
{
    cin>>n>>m;
    memset(mins,0x3f,sizeof mins);
    memset(maxs,-0x3f,sizeof maxs);
    for(int i=1;i<=n;i++) //每个点的值
    {
        cin>>w[i];
    }
    for(int i=1;i<=m;i++) //构建图
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back(b);
        ng[b].push_back(a);
        if(c==2)
        {
            g[b].push_back(a);
            ng[a].push_back(b);
        }
    }
    dfs_min(1,w[1]); //处理最小值
    dfs_max(n,w[n]); //处理最大值
    int res=0;
    for(int i=1;i<=n;i++) //枚举临界点
    {
        res=max(res,maxs[i]-mins[i]);
    }
    cout<<res;
    return 0;
}