看了下题解，发现说的tarjan+dagdp……

然后翻到第三页才发现一个dagdp

然后呢，感觉讲的不是很清楚，而且压行，用了好多玄学操
作。。

关键是还没有注释，于是果断自己来一发

喜欢我的博客就来康康

另外关于后效性的讨论：

首先这个图不存在环了，如果存在环的话，该点入队次数必然高于该点入度，这个拿来用就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

int n,m,head[100050],size;
int bd[100050],a[100050],zd[100050],zx[100500],mmx=-1,dt,cnt;
int dfn[100050],low[100050],ins[100050],ind[100500]; 
int f[100050];

stack <int> s;

struct edge{
	int next,to;
}e[1008600],looker[1008600];

void addedge(int next,int to)
{
	e[++size].next=head[next];
	e[size].to=to;
	head[next]=size;
}

void tarjan(int t)  //tarjan缩点 
{
	dfn[t]=low[t]=++dt;
	s.push(t);
	ins[t]=1;
	int i,j;
	for(i=head[t];i;i=e[i].next)
	{
		j=e[i].to;
		if(!dfn[j]) tarjan(j),low[t]=min(low[t],low[j]);
		else if(ins[j]) low[t]=min(low[t],dfn[j]);
	}
	j=0;  //j一定要清零不然有些情况要炸 比如 自环之类的  
	if(dfn[t]==low[t])
	{
		cnt++;
		while(t!=j)
		{
			j=s.top();
			s.pop();
			ins[j]=0;
			bd[j]=cnt;
		}
	}
}

void dagdp(int s)
{
	queue <int> q;
	q.push(bd[s]);
	f[bd[s]]=max(f[bd[s]],zd[bd[s]]-zx[bd[s]]);  //这个刷不刷都不用管反正都是0 
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		int i,j; 
		for(i=head[t];i;i=e[i].next)
		{
			j=e[i].to;
			ind[j]--; 
            zx[j]=min(zx[j],zx[t]);//保留这个点的最小值，因为买的时候可以从一个价格低的地方带过来。 
            f[j]=max(f[j],max(zd[j]-zx[j],f[t]));//判断一下，有三种情况 ： 从另外的点带过来，这个点卖，上个点卖 
			if(!ind[j])
			{
				q.push(j);  //当每个能刷新该点的点都被完成刷新后才可以刷这个点[无后效性原则] 
			}
		}
		
	}
}

int main()
{
	int i,j;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
	{
		int t1,t2,t3;
		scanf("%d %d %d",&t1,&t2,&t3);
		if(t3==1) 
		{
		addedge(t1,t2);
		looker[size].next=t1;
		looker[size].to=t2;	  //保留一个边集的备份，以便从新建边 
		}
		if(t3==2)
		{
		addedge(t2,t1);
		addedge(t1,t2);  //双向边不考虑，因为它们必然在一个强连通分量里面 
		} 
	}
	for(i=1;i<=n;i++)
	if(!dfn[i]) tarjan(i);
	memset(zd,-1,sizeof(zd));  //最大值赋为-1，最小值赋为0x3f3f3f3f 
	memset(zx,0x3f,sizeof(zx));
	int sz=size;
	memset(head,0,sizeof(head));
	size=0;
	for(i=1;i<=sz;i++)
	{
		int aa,bb;
		aa=looker[i].next;
		bb=looker[i].to;
		aa=bd[aa];
		bb=bd[bb];
		if(aa==bb) continue;
		addedge(aa,bb);  
		ind[bb]++; //每个点的入度就是该点最大能被刷新的次数 
	}
	for(i=1;i<=n;i++)
	{
		zd[bd[i]]=max(zd[bd[i]],a[i]);
		zx[bd[i]]=min(zx[bd[i]],a[i]);    //因为是一个强连通分量每个点可以互相通达，因此记录售价的最高和最低就可以了 
	}
	dagdp(1);
	printf("%d",f[bd[n]]);
	return 0;
}