题解 P1073 【最优贸易】
私认为这道题出的很好，综合了spfa的思想（但是不是算最短路），综合了一点点简单dp的思想，甚至还有贪心（大雾）还联系了反向建图
是一道全方位联系码力和思维的好题
综合了楼下兄弟的题解，讲的详细一点，希望能给大家带来帮助
首先我们先来分析最优贸易是如何产生的
在一条从起点到终点的路上的任意一个点，在这个点的前开后闭区间里买入，并且在前闭后开区见里抛出，最大的差价即为最优贸易
自然想到了spfa（大雾）但是spfa是依赖边权进行计算的，那怎么办，我们可以把点权赋给相邻的边权（向前向后都没关系哦）
平时的spfa是最短路，但这里的spfa是用来算到当前点的最低买入价和最高售出价格（dp思想）
坑点：1.建图是错综复杂，务必要检查清楚，如果您逻辑分析能力超强，能够理顺关系的话，私以为建一个图反着用也是可以的
2.本图是有环的！！！判断条件在里面将会将spfa卡住
3.对于每一次操作（每一条边）都应该在1.该边边权 2.起点值 3.终点值里面筛选min
4.初始化借鉴楼下兄弟很坑，不然会进入低价的死路
黏上很好看的代码，一行一行清晰明了，就不打注释了，看的眼睛痛：
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int a[100005];
struct node{
int b,next,v;
}st[1000005],nd[1000005];
int minl[100005],maxl[100005];
int n,m;
int head1[100005],head2[100005];
int now1,now2;
int vis1[100005],vis2[100005];
void add(int x,int y,int z){
now1++;
st[now1].b=y;
st[now1].v=z;
st[now1].next=head1[x];
head1[x]=now1;
}
void add2(int x,int y,int z){
now2++;
nd[now2].b=y;
nd[now2].v=z;
nd[now2].next=head2[x];
head2[x]=now2;
}
queue<int>q1;
queue<int>q2;
void spfa1(){
for(int i=1;i<=n;i++)
minl[i]=7777;
q1.push(1); //初始化借鉴题解
vis1[1]=1;
while(!q1.empty()){
int t=q1.front();
q1.pop();
vis1[t]=0;
for(int i=head1[t];i!=0;i=st[i].next){
int b=st[i].b;
if(minl[b]>min(minl[t],st[i].v)){//是在三者中找最小值，一定要把判断打在外面不然形成环spfa会卡住
minl[b]=min(minl[t],st[i].v);
if(vis1[b]==0){
q1.push(b);
vis1[b]=1;
}
}
}
}
}
void spfa2(){
for(int i=1;i<=n;i++)
maxl[i]=0;
q2.push(n);
vis2[n]=1;
while(!q2.empty()){
int t=q2.front();
q2.pop();
vis2[t]=0;
for(int i=head2[t];i!=0;i=nd[i].next){
int b=nd[i].b;
if(maxl[b]<max(maxl[t],nd[i].v)){
maxl[b]=max(maxl[t],nd[i].v);
if(vis2[b]==0){
q2.push(b);
vis2[b]=1;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==2){
add(x,y,a[y]);
add(y,x,a[x]);
add2(x,y,a[y]);
add2(y,x,a[x]);
}
else{
add2(y,x,a[x]);
add(x,y,a[y]);
}
}
spfa1();
spfa2();
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,maxl[i]-minl[i]);
}
printf("%d",ans);
return 0;
}