80pts分层图最长路求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
	int u,k,d;
	bool operator<(const node other)const{
		return d<other.d;
	}
};
int n,m;
int p[maxn];
int dis[maxn*3],vis[maxn*3];
vector<int> e[maxn*3];
void dijkstra(){
	memset(dis,-0x3f,sizeof dis);
	priority_queue<node> pq;
	dis[1]=0;
	pq.push({1,0,0});
	while(!pq.empty()){
		auto[u,k,d]=pq.top();
		pq.pop();
		if(vis[u+n*k])continue;
		vis[u+n*k]=true;
		for(auto v:e[u+n*k]){
			int ndis=d;
			if(k==0&&(v-1)/n==1){
				ndis=d-p[u];
			}else if(k==1&&(v-1)/n==2){
				ndis=d+p[u];
			}else if(k==(v-1)/n){
				ndis=d;
			}else continue;
			if(ndis>dis[v]){
				dis[v]=ndis;
				pq.push({(v-1)%n+1,(v-1)/n,ndis});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p[i];
	}
	for(int i=1,u,v,op;i<=m;i++){
		cin>>u>>v>>op;
		for(int k=0;k<3;k++){
			e[u+k*n].push_back(v+k*n);
			if(op==2)e[v+k*n].push_back(u+k*n);
		}
		e[u].push_back(v+n);
		e[u+n].push_back(v+n*2);
		if(op==2){
			e[v].push_back(u+n);
			e[v+n].push_back(u+n*2);
		}
	}
	dijkstra();
	cout<<max(0,dis[n*3])<<endl;
	return 0;
}