RT spfa

#include <bits/stdc++.h>
#define int long long
#define N 100005
#define M 500005
#define inf 0x7fffffff
#define r(a) read(a)
using namespace std;
inline void read(int &a){int f=1,x=0;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}a=x*f;return;}
int n,m,v[N],head[N],dis[N],ddis[N],cnt=0,ans;
struct edge{
	int to;
	int nxt;
}e[M];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void spfa(){
	int vis[N];
	queue<int> q;
	for (int i=1;i<=n;i++)dis[i]=inf;
	vis[1]=1;q.push(1);
	while (!q.empty()){
		int u=q.front();
		q.pop();
		dis[u]=min(dis[u],v[u]);
		for (int i=head[u];i;i=e[i].nxt){
			int tt=e[i].to;
			if (dis[u]<dis[tt]){
				dis[tt]=dis[u];
				if (!vis[tt]){
					vis[tt]=1;
					q.push(tt);
				}
			}
		}
		vis[u]=0;
	}
}
void spfa1(){
	int vis[N];
	queue<int> q;
	for (int i=1;i<=n;i++)ddis[i]=0;
	vis[n]=1;q.push(n);
	while (!q.empty()){
		int u=q.front();
		q.pop();
		ddis[u]=max(ddis[u],v[u]);
		for (int i=head[u];i;i=e[i].nxt){
			int tt=e[i].to;
			if (ddis[u]>ddis[tt]){
				ddis[tt]=ddis[u];
				if (!vis[tt]){
					vis[tt]=1;
					q.push(tt);
				}
			}
		}
		vis[u]=0;
	}
}
signed main(){
	r(n),r(m);
	for (int i=1;i<=n;i++)r(v[i]);
	for (int i=1;i<=m;i++){
		int a,b,c;r(a),r(b),r(c);
		add(a,b);
		if (c==2)add(b,a);
	}
	spfa();spfa1();
	for (int i=1;i<=n;i++)ans=max(ans,ddis[i]-dis[i]);
	printf("%lld",ans);
	return 0;
}

提交记录

求助大佬解答为什么只有10pts!谢谢