题目实在太长，（当然大家会来到我这里肯定是看过题的）就不给出了，下面给出解题思路
这道题用spfa来写，具体参考黄哲威神犇；
这道题因为要得到一个最大的旅费，而这个旅费又要通过买卖水晶球来得到，所以我们肯定是要在水晶球价格低的时候买进，高的时候卖出，这个时候就需要走两遍spfa来得到买水晶球的花费和卖水晶球的收益来得到最终的答案
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,m,sum,v[100001],last1[100001],last2[100001],mn[100001],mx[100001],d[1000001]; 6 bool used[100001]; 7 struct oo{int from,to,next1,next2;}f[1000001]; 8 void ins(int u,int v) 9 { 10 sum++; 11 f[sum].to=v; 12 f[sum].from=u; 13 f[sum].next1=last1[u]; 14 f[sum].next2=last2[v]; 15 last1[u]=sum; 16 last2[v]=sum; 17 } 18 int main() 19 { 20 memset(mn,127,sizeof(mn)); 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=n;i++) 23 scanf("%d",&v[i]); 24 for(int i=1;i<=m;i++) 25 { 26 int x,y,z; 27 scanf("%d%d%d",&x,&y,&z); 28 ins(x,y); 29 if(z==2)ins(y,x); 30 } 31 int t=0,w=0; 32 d[0]=1;mn[1]=v[1];used[1]=1; 33 while(t<=w) 34 { 35 int p=last1[d[t]]; 36 while(p>0) 37 { 38 if(mn[f[p].to]>mn[d[t]]||v[f[p].to]<mn[f[p].to]) 39 { 40 mn[f[p].to]=min(v[f[p].to],mn[d[t]]); 41 if(!used[f[p].to])d[++w]=f[p].to; 42 used[f[p].to]=1; 43 } 44 p=f[p].next1; 45 } 46 used[d[t]]=0; 47 t++; 48 } 49 memset(used,0,sizeof(used)); 50 memset(mx,-1,sizeof(mx)); 51 d[0]=n;mx[n]=v[n];used[n]=1;t=0,w=0; 52 while(t<=w) 53 { 54 int p=last2[d[t]]; 55 while(p>0) 56 { 57 if(mx[f[p].from]<mx[d[t]]||v[f[p].from]>mx[f[p].from]) 58 { 59 mx[f[p].from]=max(v[f[p].from],mx[d[t]]); 60 if(!used[f[p].from])d[++w]=f[p].from; 61 used[f[p].from]=1; 62 } 63 p=f[p].next2; 64 } 65 used[d[t]]=0; 66 t++; 67 } 68 int ans=0; 69 for(int i=1;i<=n;i++) 70 ans=max(mx[i]-mn[i],ans); 71 printf("%d",ans); 72 }