# 题目
# 题意
n 个城市，从 1 到 n 点，有有向边，也有无向边，每个城市都有宝石价格，从一个点买一个宝石，再在后面走的点卖出，问最多赚多少钱？
# 思路
对每一个路径求一个前缀最小值和后缀最大值，对每一个点后缀减去前缀取最大值即是答案，细节就是，求后缀可以反建图，开一个 rhead 数组
# CODE
#include <bits/stdc++.h> | |
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); | |
using namespace std; | |
const int MAXN=500000; | |
const int INF=0x3f3f3f3f; | |
struct node{ | |
int to,next; | |
}e[MAXN]; | |
queue<int> q; | |
int head[MAXN],val[MAXN],mi[MAXN],mx[MAXN],rhead[MAXN]; | |
int n,m,tot,s,flag=0; | |
void add(int u,int v,int head[]){ | |
e[tot]={v,head[u]}; | |
head[u]=tot++; | |
} | |
void spfa(int s){ | |
q.push(s); | |
while(!q.empty()){ | |
int fr=q.front(); | |
q.pop(); | |
int i=flag==0?head[fr]:rhead[fr]; | |
for( ;~i;i=e[i].next){ | |
int v=e[i].to; | |
if(!flag && min(mi[fr],val[v])<mi[v]){ | |
mi[v]=min(mi[fr],val[v]); | |
q.push(v); | |
} | |
else if(flag && max(mx[fr],val[v])>mx[v]){ | |
mx[v]=max(mx[fr],val[v]); | |
q.push(v); | |
} | |
} | |
} | |
} | |
int main() | |
{ | |
ios; | |
memset(head,-1,sizeof head); | |
memset(rhead,-1,sizeof rhead); | |
memset(mi,0x3f,sizeof mi); | |
cin>>n>>m; | |
for(int i=1;i<=n;i++) cin>>val[i]; | |
while(m--){ | |
int u,v,o; | |
cin>>u>>v>>o; | |
add(u,v,head); | |
add(v,u,rhead); | |
if(o==2){ | |
add(v,u,head); | |
add(u,v,rhead); | |
} | |
} | |
mi[1]=val[1]; | |
mx[n]=val[n]; | |
spfa(1); | |
flag=1; | |
spfa(n); | |
int ans=-1; | |
for(int i=1;i<=n;i++) ans=max(ans,mx[i]-mi[i]); | |
cout<<ans<<'\n'; | |
return 0; | |
} |
