思路
这题可以使用正反图 Dijkstra 来做。
假设当前位于城市 \(i\)，要使赚取的旅费最多，就需要在 \(1\to i\) 路径上选择最小的买入价，在 \(i\to n\) 路径上选择最大的卖出价。\(1\to i\) 路径上的最小点权我们很好求，直接用 Dijkstra 算法，以城市 \(1\) 为起点，求单源最短路即可。难点是如何求出 \(i\to n\) 路径上的最大点权，如果每次到达一个城市，就以这个城市为起点，用 Dijkstra 求单源最短路的话，时间复杂度达到了 \(\mathcal O(nm\log n)\)，在本题数据范围下会超时。
我们不妨反过来想，要求 \(i\to n\) 的最大点权，与其被动的一次次重复求最短路，还不如利用反向思维，建原图 \(G\) 的反图 \(G'\)，求出 \(n\to i\) 在图 \(G'\) 上的最大点权。这一方法只需要求一次最短路径，时间复杂度为 \(\mathcal O(m\log n)\)，再加上求 \(1\to i\) 的最小点权的时间复杂度，总时间复杂度就是 \(\mathcal O(2m\log n)\)，足以通过本题。
代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;template<typename T=int>
T rd(){char ch=getchar();T x=0,f=1;while(!isdigit(ch)){if(ch=='-') f*=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+5,M=2e6+5;struct edge{int to,nxt;
} g[M];int n,m,tot,a[N],pre[2][N],dist[2][N];
bitset<N> vis;void add(int pre[ ],int u,int v){g[++tot].to=v;g[tot].nxt=pre[u];pre[u]=tot;
}void spfa(int dist[ ],bool b,int pre[ ]){vis.reset();queue<int> q;if(!b){ //最小值memset(dist,0x3f,4*N);q.push(1);dist[1]=a[1];} else{ //最大值memset(dist,0xcf,4*N);q.push(n);dist[n]=a[n];}while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=pre[x];i;i=g[i].nxt){int y=g[i].to;if(!b&&dist[y]>min(dist[x],a[y])){dist[y]=min(dist[x],a[y]);if(!vis[y]) q.push(y),vis[y]=1;} else if(b&&dist[y]<max(dist[x],a[y])){dist[y]=max(dist[x],a[y]);if(!vis[y]) q.push(y),vis[y]=1;}}}
}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(pre[0],u,v),add(pre[1],v,u);if(w==2) add(pre[0],v,u),add(pre[1],u,v);}spfa(dist[0],0,pre[0]);spfa(dist[1],1,pre[1]);int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dist[1][i]-dist[0][i]);cout<<ans<<endl;return 0;
}