这么经典的题目，还是看了lyd的题解....唉难过。
一句话题意：在一张点有全都的图上找一条从1到n的路径，存在两个点p,q(p<q),使val[q]-val[p]最大。
给出的图是既有双向又有单向的混合图，考虑像普通的方法一样建图。除此之外，再在一个新邻接表中建原图的反图（边方向相反）。
为什么要这样做？
考虑分别自起点到终点和自终点到起点遍历，计算出f[]和d[]，其中f[i]表示从1到i的路径中经过的最小的点权，d[i]表示从n到i的路径中经过的最大点权。（想一想，为什么？）
于是我们就可以枚举断点X,使d[x]-f[x]最大。保证了1能走到n，即路径的连贯（联通）性。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 100090
#define maxm 500090 using namespace std; int n,m,totp,totn,ans;
int headp[maxn],headn[maxn],val[maxn],f[maxn],d[maxn],vis[maxn];
struct node{
int to,next;
};
node edge_posi[maxm*],edge_nega[maxm*]; void add_posi(int x,int y)
{
edge_posi[++totp].to=y;
edge_posi[totp].next=headp[x];
headp[x]=totp;
} void add_nega(int x,int y)
{
edge_nega[++totn].to=y;
edge_nega[totn].next=headn[x];
headn[x]=totn;
} void spfa_posi()
{
queue<int>q;
memset(d,0x3f,sizeof(d));
q.push();d[]=val[];vis[]=;
while(!q.empty())
{
int x=q.front();
q.pop();vis[x]=;
for(int i=headp[x];i;i=edge_posi[i].next)
{
int y=edge_posi[i].to;
if(min(d[x],val[y])<d[y])
{
d[y]=min(d[x],val[y]);
if(!vis[y]) q.push(y),vis[y]=;
}
}
}
} void spfa_nega()
{
queue<int>q;
memset(vis,,sizeof(vis));
memset(f,,sizeof(f));
q.push(n);d[n]=val[n];vis[n]=;
while(!q.empty())
{
int x=q.front();
q.pop();vis[x]=;
for(int i=headn[x];i;i=edge_nega[i].next)
{
int y=edge_nega[i].to;
if(max(f[x],val[y])>f[y])
{
f[y]=max(f[x],val[y]);
if(!vis[y]) q.push(y),vis[y]=;
}
}
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&val[i]);
for(int i=;i<=m;i++)
{
int x=,y=,opt=;
scanf("%d%d%d",&x,&y,&opt);
if(opt==)
{
add_posi(x,y);
add_nega(y,x);
}
else if(opt==)
{
add_posi(x,y);add_posi(y,x);
add_nega(y,x);add_nega(x,y);
}
}
spfa_posi();
spfa_nega();
for(int i=;i<=n;i++)
ans=max(ans,f[i]-d[i]);
printf("%d",ans);
return ;
}
建反图的思想妙啊！