我们看一下这个题的要求。首先就是我们只可以买一次，卖一次，而且我们还必须得到达终点，那我们不妨进行两遍最短路，第一次计算从起始点开始到所有点能买物品的最低价格（用dis[i]表示），第二次计算从终点到所有点能卖物品的最高价格(用dis1[i]表示)。这样两遍跑一次然后结果就是max（dis1[i] - dis[i]）第二次跑要在反图上跑。
所以跑两遍dij就行（这个图的边和点比较多所以还是用dij吧，这题比较久远所以用spfa好像不会被卡，但是现在就说不好了……）然后我们要使用两个堆……所以我们还不如直接写优先队列版的，抛弃一下set（因为我不知道怎么重载set……）在每个函数里面直接把优先队列重载使用pair就可以，剩下的都一样，更新的判断条件为dis[i] = min/max(dis[i],c[i],dis[k])，k是上次转移来的点，c存储这个位置的价值。
看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #include<utility> #include<map> #define pr pair<int,int> #define mp make_pair #define fi first #define sc second #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 100005; const int N = 500005; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int to,next,from; }e[N<<1],e1[N<<1]; int c[M],head[M],x,y,z,ecnt,ecnt1,head1[M],dis[M],dis1[M],maxn,n,m; bool vis[M]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].from = x; e[ecnt].next = head[x]; head[x] = ecnt; } void add1(int x,int y) { e1[++ecnt1].to = y; e1[ecnt1].from = x; e1[ecnt1].next = head1[x]; head1[x] = ecnt1; } void dij(int s) { rep(i,1,n) dis[i] = INF; dis[s] = c[s]; priority_queue<pr,vector<pr>,greater<pr> > q; q.push(mp(dis[s],s)); while(!q.empty()) { int k = q.top().sc;q.pop(); if(vis[k]) continue; vis[k] = 1; for(int i = head[k];i;i = e[i].next) { int g = min(dis[k],c[e[i].to]); if(dis[e[i].to] > g) dis[e[i].to] = g,q.push(mp(dis[e[i].to],e[i].to)); } } } void dij1(int s) { memset(vis,0,sizeof(vis)); dis1[s] = c[s]; priority_queue<pr> q; q.push(mp(dis1[s],s)); while(!q.empty()) { int k = q.top().sc;q.pop(); if(vis[k]) continue; vis[k] = 1; for(int i = head1[k];i;i = e1[i].next) { int g = max(dis1[k],c[e1[i].to]); if(dis1[e1[i].to] < g) dis1[e1[i].to] = g,q.push(mp(dis1[e1[i].to],e1[i].to)); } } } int main() { n = read(),m = read(); rep(i,1,n) c[i] = read(); rep(i,1,m) { x = read(),y = read(),z = read(); add(x,y),add1(y,x); if(z == 2) add(y,x),add1(x,y); } dij(1),dij1(n); rep(i,1,n) maxn = max(maxn,dis1[i] - dis[i]); printf("%d ",maxn); return 0; }