AC subtask#0 #1 #4 #7 subtask#1

其余wa

#include<bits/stdc++.h>
using namespace std;
#define ine long long

const int N = 1e4 + 10,M = 5e4 + 10,inf = 1e10;;

int n,m,head[N],tot,a[N],b,ans = inf;
bool vis[N];

struct node
{
	int u,v,w;
}edge[M<<2];

struct qqq
{
	int u,cnt,xp;
};

bool operator<(qqq a,qqq b)
{
	return (a.cnt==b.cnt)?(a.xp<b.xp):(a.cnt<b.cnt);
}

void add(int u,int v,int w)
{
	edge[++tot] = {head[u],v,w};
	head[u] = tot;
}

void dij(int o)
{
	priority_queue<qqq> q;
	q.push({1,a[1],b});
	while(!q.empty())
	{
		int u = q.top().u,cnt = q.top().cnt,xp = q.top().xp;
		q.pop();
		if(vis[u]||xp<0)
		{
			continue;
		}
		if(u==n)
		{
			ans = min(ans,cnt);
			continue;
		}
		vis[u] = 1;
		for(int i = head[u];i;i = edge[i].u)
		{
			int v = edge[i].v,w = edge[i].w;
			q.push({v,max(cnt,a[v]),xp-w});
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>b;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i = 1,u,v,w;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dij(1);
	if(ans==inf)
	{
		cout<<"AFK"<<endl;
	}
	else
	{
		cout<<ans<<endl;
	}
}