#2 #6 #10

虽说写的是 MLE，但是本地测也是 TLE

如果分层图过不了就直接说吧哈哈，反正也是乱写的

代码如下：

// Problem: P1073 [NOIP2009 提高组] 最优贸易
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1073
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
//#define int long long
using namespace std;
int read(){
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*w;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10)print(x/10);
	putchar(x%10+'0');
	return;
}
int n,m;
struct Edge{
	int v,w,next;
}edge[3000010];//i+0*n->l1 i+1*n->l2 i+2*n->l3
int head[100010],dis[300010],cut;
priority_queue<pair<int,int> >q;
void add_edge(int u,int v,int w){
	edge[++cut].v=v;
	edge[cut].w=w;
	edge[cut].next=head[u];
	head[u]=cut;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int ls=read();
		add_edge(i,i+n,100-ls);
		add_edge(i+n,i+2*n,100+ls);
		//用dijk非得是正的边权
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),type=read();
		add_edge(u,v,0);
		add_edge(u+n,v+n,0);
		add_edge(u+2*n,v+2*n,0);
		if(type==2){
			add_edge(v,u,0);
			add_edge(v+n,u+n,0);
			add_edge(v+2*n,u+2*n,0);
		}
	}
	for(int i=2;i<=3*n;i++)dis[i]=-1;
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			//cerr<<u<<" "<<v<<" "<<w<<"\n";
			if(dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	print(max(dis[n],dis[n*3])-200);
	return 0;
}