本文共 1948 字，大约阅读时间需要 6 分钟。

题目

Input

Output

Sample Input

5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2 

Sample Output

5

link

解题思路

一道非常猥琐的题，卡了我一晚上。。。c

题目大意：从$1$走到$n$，中途要买一次，卖一次，求最大利润

以小学知识可知，买得越便宜，卖得越贵，利润越大
把$1$ ~ $n$以$k$为标准，分成两段。$1$ ~ $k$买，$k$ ~ $n$卖，$k$需要枚举

买：做一遍SPFA，把每个点的最小售价求出来

卖：如果每个枚举出来的$k$都做一遍SPFA，求$k$ ~ $n$的卖价，会T。so，先反图，再从$n$做SPFA，把每个点的最大售价求出来。然后再枚举$k$，用$n$ ~ $k$的最大售价减去$1$ ~ $k$的最小售价。

Code

#include<iostream>#include<cstdio>#include<cstring>using namespace std;struct DT{   	int to,next;}a[10000000],b[10000000];int h,t,v[10000000],f[1000100];int dis_max[1000100],dis_min[1000100],heada[1000100],headb[1000100],s[1000100],n,m,num,Gun;//数据大到猥琐void SPFA_min(){   	h=0,t=1,v[1]=1,f[1]=1,dis_min[1]=s[1];	while(h++<t){   		for(int i=heada[v[h]];i;i=a[i].next){   			if(min(s[a[i].to],dis_min[v[h]])<dis_min[a[i].to]){   //不是最短路，是求最小				dis_min[a[i].to]=min(s[a[i].to],dis_min[v[h]]);		        if(!f[a[i].to]){   		        	f[a[i].to]=1;		        	v[++t]=a[i].to;		    	}		    }		}		f[v[h]]=0;	}}void SPFA_max(){   	h=0,t=1,v[1]=n,f[n]=1,dis_max[n]=s[n];	while(h++<t){   		for(int i=headb[v[h]];i;i=b[i].next){   			if(max(s[b[i].to],dis_max[v[h]])>dis_max[b[i].to]){   //求最大				dis_max[b[i].to]=max(s[b[i].to],dis_max[v[h]]);	    		if(!f[b[i].to]){   	    			f[b[i].to]=1;	     			v[++t]=b[i].to;	    		}			}		}		f[v[h]]=0;	}}int main(){   	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)	    scanf("%d",&s[i]); 	for(int i=1;i<=m;i++){   		int x,y,z;		scanf("%d%d%d",&x,&y,&z);		a[++num].to=y,a[num].next=heada[x],heada[x]=num;//a是正图		b[num].to=x,b[num].next=headb[y],headb[y]=num;//b是反图		if(z==2){   //无向图			a[++num].to=x,a[num].next=heada[y],heada[y]=num;			b[num].to=y,b[num].next=headb[x],headb[x]=num;		}	}	memset(f,0,sizeof(f));	memset(dis_min,0x7f,sizeof(dis_min));	SPFA_min();	memset(f,0,sizeof(f));	SPFA_max();	for(int i=2;i<n;i++)//我也不知道为什么不能求n	       Gun=max(Gun,dis_max[i]-dis_min[i]);	printf("%d",Gun); }