记录编号	519000	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.497 s
提交时间	2018-10-31 20:03:03	内存使用	5.44 MiB

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
const int N=100000;
int n,m,k,l;
vector<int> g[N];
int cost[N],mi[N],f[N];
void dfs(int x,int minx,int pre)//x表示当前的点，minx表示当前找到的最大值，pre前驱 
{ int flag=1;
  if (cost[x]<minx) {minx=cost[x];flag=0;}// 找到当前的最小值进行更新
  int maxx=max(f[pre],cost[x]-minx); 
  if (maxx>f[x]) {f[x]=maxx;flag=0;}//进行动态规划，进行更新 
  if (flag) return;//判断是否这次有什么变化 
  for (int i=0;i<g[x].size();i++)
  dfs(g[x][i],minx,x);//继续进行dfs 
}
int main()
{ freopen("trade.in","r",stdin);
  freopen("trade.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++)
  scanf("%d",&cost[i]);
  for (int i=1;i<=m;i++)
  { int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    g[x].push_back(y);
    if (z==2) g[y].push_back(x);//初始化 
  }
  dfs(1,INF,0);
  printf("%d",f[n]);
  return 0;
}