题意：多个节点，起点到终点，每个点可以买或卖水晶球，每个点水晶球的价格不一样（买卖价格相同）。问最多买卖一次，能赚取最高多少差价？（在赚不到差价的情况下他就无需进行贸易）。
思路：“这个'b'题，我不看题解我是想不出来，但是确实是个很好的题”。有两种做法，双向spfa和分层图，我就只说分层图做法（另一个也不会）。
分层图是多层，每层代表了不同的状态。这里有3层。
一层之间权值都=0，一层到二层是买入，二层到三层是卖出。
分层图就是存图麻烦，然后就是正常跑一个spfa(spfa是能处理负边的，具有伸缩，dij是不能的)就可以了。题解注释的那一块是输出存的题，不懂了是如何存图的，可以输出看看，会是这样：
题解：
点击查看代码
//S 分层图
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+9;
int n,m,U,V,T,c;
vector<int>dis(N,-INT64_MAX),vis(N,0);//与dij的vis不同，此vis是判断节点i是否在队列中.
// 这里是spfa找到终点最大值，dis数组要初始化极小值。
vector<pair<int,int>>G[N];//first:点 second:权值
void spfa(){
queue<int>q;
q.push(1);
dis[1]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto [x,y]:G[u]){//u-->x
if(dis[x]<dis[u]+y){//比较是否有更大值
dis[x]=dis[u]+y;
if(!vis[x]){
q.push(x),vis[x]=1;
}
}
}
}
}
signed main()
{
scanf("%lld%lld",&n,&m);
int n2=n*2;
for(int i=1;i<=n;i++){//层与层之间只能单向图
scanf("%lld",&c);
G[i].push_back({n+i,-c});//一层
G[n+i].push_back({n2+i,c});//二层
}
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&U,&V,&T);
G[U].push_back({V,0});
G[n+U].push_back({n+V,0});
G[n2+U].push_back({n2+V,0});
if(T==2){//双向图
G[V].push_back({U,0});
G[n+V].push_back({n+U,0});
G[n2+V].push_back({n2+U,0});
}
}
// for(int i=1;i<=3*n;i++){
// cout<<i<<":";
// for(auto x:G[i]){
// cout<<x.first<<","<<x.second<<";";
// }
// cout<<endl;
// }
spfa();
printf("%lld\n",dis[3*n]);
return 0;
}