题目：https://www.luogu.org/problemnew/show/P1073
由于任何城市都可以多次经过，所以可以随便走，也就不用太在意有向边和无向边，把无向边当做两条有向边处理；
根据题意，价格较小的城市要先于价格较大的城市被经过，然而它又可以随便走，所以不妨分开考虑；
每个点维护两个值，一个是从起点到它的最小值，一个是从终点到它的最大值，在每个城市的二者之差中取MAX即可；
于是问题转化为求两个单源最短路，对于终点出发的那个，将边全部反向进行最短路即可。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; priority_queue< pair<int,int> >q; int const MAXN=1e5+5,MAXM=5e5+5; int n,m,head[MAXN],ct,s[MAXN],t[MAXN],head2[MAXN],ct2,cost[MAXN],ans; bool vis[MAXN]; struct N{ int to,next; N(int t=0,int n=0):to(t),next(n) {} }edge[MAXM],edge2[MAXM]; void add(int x,int y,int z) { edge[++ct]=N(y,head[x]);head[x]=ct; edge2[++ct2]=N(x,head2[y]);head2[y]=ct; if(z==2) { edge[++ct]=N(x,head[y]);head[y]=ct; edge2[++ct2]=N(y,head2[x]);head2[x]=ct; } } void dijkstra1() { while(q.size())q.pop(); memset(s,0x3f,sizeof s); memset(vis,0,sizeof vis); s[1]=cost[1];q.push(make_pair(-cost[1],1));//大根堆 while(q.size()) { int x=q.top().second;q.pop(); if(vis[x])continue;//! vis[x]=1; for(int i=head[x],u;i;i=edge[i].next) if(s[u=edge[i].to]>min(s[x],cost[u])) { s[u]=min(s[x],cost[u]); q.push(make_pair(-s[u],u)); } } } void dijkstra2() { while(q.size())q.pop(); memset(t,-3,sizeof t); memset(vis,0,sizeof vis); t[n]=cost[n];q.push(make_pair(cost[n],n));//大根堆 while(q.size()) { int x=q.top().second;q.pop(); if(vis[x])continue;//! vis[x]=1; for(int i=head2[x],u;i;i=edge2[i].next) if(t[u=edge2[i].to]<max(t[x],cost[u])) { t[u]=max(t[x],cost[u]); q.push(make_pair(t[u],u)); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&cost[i]); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dijkstra1(); dijkstra2(); for(int i=1;i<=n;i++) ans=max(ans,t[i]-s[i]); printf("%d",ans); return 0; }