题目链接：https://www.luogu.com.cn/problem/P1073

 

设f[i][0/1]，

f[i][0]表示走到i点的最小价格，f[i][1]表示走到i点的最大收益（差值）。转移过于简单。

注意DFS中的剪枝。

 

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=100005;
 6 int n,m,tot;
 7 int head[N],a[N],f[N][2];
 8 struct node{
 9     int to,next;
10 }edge[N*10];
11 void add(int u,int v){
12     edge[tot].to=v;
13     edge[tot].next=head[u];
14     head[u]=tot++;
15 }
16 void DFS(int u,int minn,int pre){
17     int flag=1;
18     minn=min(minn,a[u]);
19     if(minn<f[u][0]) f[u][0]=minn,flag=0;
20     int maxn=max(f[pre][1],a[u]-minn);
21     if(f[u][1]<maxn) f[u][1]=maxn,flag=0;
22     if(flag) return;
23     for(int i=head[u];i!=-1;i=edge[i].next){
24         int v=edge[i].to;
25         DFS(v,minn,u);
26     }
27 }
28 int main(){
29     memset(head,-1,sizeof(head));
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=n;i++) f[i][0]=0x7f7f7f;
32     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
33     for(int i=1;i<=m;i++){
34         int x,y,z;
35         scanf("%d%d%d",&x,&y,&z);
36         add(x,y);
37         if(z==2) add(y,x);
38     }
39     DFS(1,0x7f7f7f,0);
40     printf("%d",f[n][1]);
41     return 0;
42 }

AC代码