题目传送门：洛谷P1073
dalao们都用的tarjan啊拓扑排序啊之类的玩意儿，我这个蒟蒻不会，只想到了极其暴力的分层图最短路
设三个状态
0表示没有发生任何买卖的情况
1表示买了没有卖的情况
2表示已经卖了的情况
这样建出来一个3层的图，用dis[i][j]表示从起点到i点，处在j状态下获得的最大收益
状态转移方程：//id就是从哪个点来
对于所有的状态，都可以在同状态下相互更新dis值，所以
dis[to][sit]=max(dis[to][sit],dis[id][sit])
状态1可以由状态0时购买水晶球得到，购买是减收益，所以
dis[to][1]=max(dis[to][1],dis[id][0]-pri[to])
状态2可以由状态1时卖出水晶球得到，卖出增加了收益，所以
dis[to][2]=max(dis[to][2],dis[id][1]+pri[to])
注意有可能会出现不买不卖的情况，也就可以理解为在某一点买了马上又卖，给每个点加个自环就可以处理这种情况了
观察状态转移方程，发现有负权边，不能用dijkstra，所以spfa走起
最后输出dis[n][2]，终点的状态2
AC代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; const int INF=;
int n,m=;
struct star{//链式前向星
int u,v;
}edge[];
int last[],next[];
void addedge(int u,int v){//加边
m++;
edge[m]=(star){u,v};
}
void starinit(){//前向星初始化
for(int i=;i<=n;i++) last[i]=-;
for(int i=;i<=m;i++){
int flag=edge[i].u;
next[i]=last[flag];
last[flag]=i;
}
}
int pri[];//每个点水晶球的价格 struct mem{
int id,sit;
}que[];
int head,tail;
void push(mem pig){
que[tail]=pig;tail++;
}
void pop(){head++;} int dis[][],book[][];
void spfa(int sta){
head=;tail=;
for(int i=;i<=n;i++){dis[i][]=-INF;dis[i][]=-INF;dis[i][]=-INF;book[i][]=;book[i][]=;book[i][]=;}
dis[][]=;
book[sta][]=;
push((mem){sta,});
for(;head<tail;){ int id=que[head].id;
int sit=que[head].sit;
for(int i=last[id];i!=-;i=next[i]){
int to=edge[i].v;
if(dis[to][sit]<dis[id][sit]){//通用转移方程
dis[to][sit]=dis[id][sit];
if(book[to][sit]==){
book[to][sit]=;
push((mem){to,sit});
}
}
switch(sit){
case :{
if(dis[to][]<dis[id][]-pri[to]){//0->1
dis[to][]=dis[id][]-pri[to];
if(book[to][]==){
book[to][]=;
push((mem){to,});
}
}
break;
}
case :{
if(dis[to][]<dis[id][]+pri[to]){//1->2
dis[to][]=dis[id][]+pri[to];
if(book[to][]==){
book[to][]=;
push((mem){to,});
}
}
break;
}
}
}
book[id][sit]=;
pop();
}
} int main(){
m=;
int cirno;
cin>>n>>cirno;
for(int i=;i<=n;i++){
scanf("%d",&pri[i]);
}
for(int i=;i<=cirno;i++){
int u,v,type;
scanf("%d%d%d",&u,&v,&type);
addedge(u,v);
if(type==) addedge(v,u);
}
for(int i=;i<=n;i++) addedge(i,i);//加自环
starinit();
spfa();
cout<<dis[n][];
return ;
}
/*
自测
7 8
9 2 3 2 10 1 7
1 2 1
2 3 1
3 7 1
7 6 1
6 3 1
7 4 1
4 5 1
5 3 1
*/