P1073
最短路
题目传送门
具体思路（参考了《算法竞赛进阶指南》）：
开两个数组 f1[x]，f2[x] 分别表示 从1到x的最小买入价格，从x到n的最大卖出价格。
然后建两张图（一正一反），跑两遍SPFA或heap-dijkstra求两个数组，这里的条件不再是边权而改为了点权，所以不说是求最短路。
疯狂挂初始化，一上来默认数组初值为初始价格，后来发现并不是所有点都可以到，所以在维护的过程中，每取出一个点就与其初始价格比较即可，这样既避免了默认全部点可以到，也避免了计算不了该点初始价格。。算了不说了语文太差
代码（好长啊）
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 100001
#define maxm 500001
#define re register
using namespace std;
int read()
{
int fu=1,num=0; char c; c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') fu=-1,c=getchar();
while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
return fu*num;
}
struct edge{
int to,next;
};
edge e1[maxm*2],e2[maxm*2];
queue <int> q;
int f1[maxn],f2[maxn],n,m,ans,p[maxn],tot1,last1[maxn],tot2,last2[maxn];
bool vis[maxn],b[maxn];
void add_edge(int x,int y)
{
tot1++; e1[tot1].to=y; e1[tot1].next=last1[x]; last1[x]=tot1;
tot2++; e2[tot2].to=x; e2[tot2].next=last2[y]; last2[y]=tot2;
}
void init()
{
n=read(); m=read();
for(re int i=1;i<=n;i++) p[i]=read();
for(re int i=1;i<=m;i++)
{
int u,v,z;
u=read(); v=read(); z=read();
if(z==1) add_edge(u,v);
else
{
add_edge(u,v); add_edge(v,u);
}
}
}
void spfa_work()
{
memset(f1,0x3f,sizeof(f1));
q.push(1);
while(!q.empty())
{
int x=q.front(); q.pop(); vis[x]=0;
f1[x]=min(f1[x],p[x]);
for(re int i=last1[x];i;i=e1[i].next)
if(f1[x]<f1[e1[i].to])
{
f1[e1[i].to]=f1[x];
if(!vis[e1[i].to])
{
q.push(e1[i].to);
vis[e1[i].to]=1;
}
}
}
q.push(n);
while(!q.empty())
{
int x=q.front(); q.pop(); vis[x]=0;
f2[x]=max(f2[x],p[x]);
for(re int i=last2[x];i;i=e2[i].next)
if(f2[x]>f2[e2[i].to])
{
f2[e2[i].to]=f2[x];
if(!vis[e2[i].to])
{
q.push(e2[i].to);
vis[e2[i].to]=1;
}
}
}
}
int main()
{
init();
spfa_work();
ans=0;
for(re int i=1;i<=n;i++) if(f2[i]!=f2[0])ans=max(ans,f2[i]-f1[i]);
cout<<ans<<endl;
return 0;
}