freopen不用管，提交时已去除
by Ouaoan @ 2018-10-31 21:49:39
先orz一发小姐姐QwQ
by Rbu_nas @ 2018-10-31 21:54:45
QwQ
by Ouaoan @ 2018-10-31 21:55:27
@[渣儿](/space/show?uid=13117) 您太强了 小蒟蒻写不来 爱莫能助QAQ
by Rbu_nas @ 2018-10-31 21:56:20
@[渣儿](/space/show?uid=13117) 前排不会+%大佬
by 引领天下 @ 2018-10-31 22:17:39
这题不是电风扇吗……
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
const int SIZE=100005;
int n,m,price[SIZE],dp[SIZE],x,y,z;
vector <int> way[SIZE];
void dfs(int now,int minp,int last){
minp=min(minp,price[now]);
int maxn=max(dp[last],price[now]-minp);
if(dp[now]<maxn) dp[now]=maxn;
else return;
for(int i=0;i<way[now].size();i++) dfs(way[now][i],minp,now);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&price[i]);
dp[i]=-1;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
way[x].push_back(y);
if(z==2) way[y].push_back(x);
}
dfs(1,1<<30,0);
printf("%d\n",dp[n]);
return 0;
}
```
by Jameswood @ 2018-10-31 22:34:16
@[渣儿](/space/show?uid=13117) 请问 zar dalao 调出来了吗？当时我用 tarjan 也是 20，三天没调出来，放起来 o(TヘTo)
by Anguei @ 2018-11-01 07:08:19
@[Anguei](/space/show?uid=53062) zar蒟蒻没调出来啊……QwQ
by Ouaoan @ 2018-11-01 14:59:29
@[Anguei](/space/show?uid=53062) zar蒟蒻没调出来啊……QwQ
by Ouaoan @ 2018-11-01 14:59:45
@[Anguei](/space/show?uid=53062) 过了过了！QAQ
by Ouaoan @ 2018-11-01 15:51:45