我用的是链式前向星存图,思路基本按这边题解的来。这段代码的问题好像是无法正常地存相邻的两层图之间的边，不知道为什么。再存相邻的两层图之间的边的时候最开始调用出的数组$head$的值都为$0$，而数组$head$的值前面都初始化为$-1$过了。奇怪的是，在后面存同一层图的边时，最开始调用出的数组$head$的值都正常地为$-1$.

#include<bits/stdc++.h>

using namespace std;

const int N=100003;
const int M=500003;
const int inf=0x8f8f8f8f;

struct node{
	int to,w,next;
}li[M*2*3+N*2];

int n,m,f[N],head[N*3],lit,x,y,z,dis[N*3],sf[N*3];

void add(int A,int B,int toward,int edge_weight);

int main(){

	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&f[i]);
		add(i,i+n,1,(-1)*f[i]),//第一层图到第二层图
		add(i+n,i+(n*2),1,f[i]);
		
		//初始化：
		dis[i]=dis[i+n]=dis[i+(n*2)]=inf,
		head[i]=head[i+n]=head[i+(n*2)]=-1,
		sf[i]=sf[i+n]=sf[i+(n*2)]=false;
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z,0),//第一层图
		add(x+n,y+n,z,0),//第二层图
		add(x+(n*2),y+(n*2),z,0);//第三层图
	}

	queue<int> q;
	q.push(1);
	dis[1]=0,sf[1]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		sf[u]=false;
		for(int i=head[u];i!=-1;i=li[i].next)
			if(dis[li[i].to]<dis[u]+li[i].w){
				dis[li[i].to]=dis[u]+li[i].w;
				if(sf[li[i].to]==false){
					sf[li[i].to]=true;
					q.push(li[i].to);
				}
			}
	}
	
	if(dis[n*3]<=0)
		printf("0");
	else
		printf("%d",dis[n*3]);

	return 0;
	
}

void add(int a,int b,int td,int ew){
	
	li[++lit]=(node){b,ew,head[a]};
	head[a]=lit;
	
	if(td==2){
		li[++lit]=(node){a,ew,head[b]};
		head[b]=lit;
	}
	
}