题目传送门：洛谷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=1147483647; int n,m=0; struct star{//链式前向星 int u,v; }edge[1000005]; int last[1000005],next[1000005]; void addedge(int u,int v){//加边 m++; edge[m]=(star){u,v}; } void starinit(){//前向星初始化 for(int i=1;i<=n;i++) last[i]=-1; for(int i=1;i<=m;i++){ int flag=edge[i].u; next[i]=last[flag]; last[flag]=i; } } int pri[1000005];//每个点水晶球的价格 struct mem{ int id,sit; }que[5000005]; int head,tail; void push(mem pig){ que[tail]=pig;tail++; } void pop(){head++;} int dis[1000005][5],book[1000005][5]; void spfa(int sta){ head=0;tail=0; for(int i=1;i<=n;i++){dis[i][0]=-INF;dis[i][1]=-INF;dis[i][2]=-INF;book[i][0]=0;book[i][1]=0;book[i][2]=0;} dis[1][0]=0; book[sta][0]=1; push((mem){sta,0}); for(;head<tail;){ int id=que[head].id; int sit=que[head].sit; for(int i=last[id];i!=-1;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]==0){ book[to][sit]=1; push((mem){to,sit}); } } switch(sit){ case 0:{ if(dis[to][1]<dis[id][0]-pri[to]){//0->1 dis[to][1]=dis[id][0]-pri[to]; if(book[to][1]==0){ book[to][1]=1; push((mem){to,1}); } } break; } case 1:{ if(dis[to][2]<dis[id][1]+pri[to]){//1->2 dis[to][2]=dis[id][1]+pri[to]; if(book[to][2]==0){ book[to][2]=1; push((mem){to,2}); } } break; } } } book[id][sit]=0; pop(); } } int main(){ m=0; int cirno; cin>>n>>cirno; for(int i=1;i<=n;i++){ scanf("%d",&pri[i]); } for(int i=1;i<=cirno;i++){ int u,v,type; scanf("%d%d%d",&u,&v,&type); addedge(u,v); if(type==2) addedge(v,u); } for(int i=1;i<=n;i++) addedge(i,i);//加自环 starinit(); spfa(1); cout<<dis[n][2]; return 0; } /* 自测 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 */