我的思路是bfs/dfs+spfa
第一遍判断每个点能否到达n
第二遍找出：每个点，能到达这个点的所有点中价格最小是多少，在这个点卖掉最多能赚多少钱
上代码：（前面一大坨自定义不要管^_^
1 #include<bits/stdc++.h> 2 namespace ZDY{ 3 #define fre freopen("test.in","r",stdin) 4 #define ll long long 5 #define db double 6 #define Fur(i,x,y) for(int i=x;i<=y;i++) 7 #define fur(i,x,y) for(i=x;i<=y;i++) 8 #define Fdr(i,x,y) for(int i=x;i>=y;i--) 9 #define in2(x,y) in(x),in(y) 10 #define in3(x,y,z) in2(x,y),in(z) 11 #define in4(a,b,c,d) in2(a,b);in2(c,d) 12 #define clr(x,y) memset(x,y,sizeof(x)) 13 #define cpy(x,y) memcpy(x,y,sizeof(x)) 14 #define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt) 15 #define inf 2147483647 16 } 17 namespace FAST{ 18 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0) 19 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0) 20 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1)) 21 namespace fib{char b[300000]= {},*f=b;}namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}struct foce{~foce(){pob;fflush(stdout);}} _foce;namespace ib{char b[100];}template<class T>inline void in(T &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}template<class T>inline void out(T x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}template<class T>inline void outn(T x){out(x);pc(' ');}inline char sc(){char c=gc;while(!(('A'<=c&&c<='Z')||('a'<=c&&c<='z')||('0'<=c&&c<='9')))c=gc;return c;} 22 template<class T>inline T ABS(T x){return x>0?x:-x;} 23 template<class T>inline T MAX(T x,T y){return x>y?x:y;} 24 template<class T>inline T MIN(T x,T y){return x<y?x:y;} 25 template<class T>inline T GCD(T x,T y){return y?GCD(y,x%y):x;} 26 template<class T>inline void swap(T x,T y){T t=x;y=t;x=y;} 27 }using namespace FAST;using namespace ZDY;using namespace std; 28 #define N 100001 29 int val[N],head[N],Head[N],cnt=0,n,m,ans=0,q[N*3],f[N]; 30 bool b[N],v[N]; 31 struct edge{int nxt,to;}e[1000001],E[1000001]; 32 inline void add(int x,int y){ 33 e[++cnt].to=y;E[cnt].to=x; 34 e[cnt].nxt=head[x];E[cnt].nxt=Head[y]; 35 head[x]=Head[y]=cnt; 36 } 37 inline void bfs(){ 38 int h=0,t=1,x; 39 q[0]=n;b[n]=1; 40 while(h<t){ 41 x=q[h++]; 42 for(int i=Head[x],to;to=E[i].to,i;i=E[i].nxt) 43 if(!b[to])b[to]=1,q[t++]=to; 44 } 45 } 46 inline void bfs2(){ 47 int h=0,t=1,x; 48 q[0]=1; 49 while(h<t){ 50 x=q[h++];ans=MAX(ans,val[x]-f[x]); 51 fl(i,x) 52 if((f[x]<f[to]||!v[to])&&b[to])f[to]=MIN(f[x],f[to]),q[t++]=to; 53 } 54 } 55 int main(){ 56 fre; 57 in2(n,m); 58 Fur(i,1,n)in(val[i]),f[i]=val[i]; 59 int x,y,z; 60 Fur(i,1,m){ 61 in3(x,y,z); 62 add(x,y);if(z==2)add(y,x); 63 } 64 bfs(); 65 bfs2(); 66 outn(ans); 67 }