#include<iostream> 
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;

int read()
{
	int sum = 0,fg = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-')fg = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * fg; 
}
const int Max = 10004;
int f[Max];
struct node
{
	int y,ne;
	int z;
}a[Max * 10];
int head[Max],sum = 0;
void add(int x,int y,int z)
{
	a[++ sum].y = y;
	a[sum].ne = head[x];
	a[sum].z = z;
	head[x] = sum;
}

struct point
{
	int x;
	int w;
	bool operator < (const point xx) const 
	{
		return xx.w < w;
	}
};
int dis[Max];
bool use[Max];
priority_queue<point>q;
int n,m,hp;
bool check(int mid)
{
	memset(dis,0x3f,sizeof(dis));
	memset(use,false,sizeof(use));
	dis[1] = 0;
	q.push((point){1,0});
	while(!q.empty())
	{
		int x = q.top().x;
		q.pop();
		if(use[x] == true)
			continue;
		use[x] = true;
		for(register int i = head[x];i != 0;i = a[i].ne)
		{
			int awa = a[i].y;
			if(dis[awa] > dis[x] + a[i].z && f[awa] <= mid)
			{
				dis[awa] = dis[x] + a[i].z;
				if(use[awa] == false)
					q.push((point){awa,dis[awa]});
			}
		}
	}
	if(dis[n] < hp)
		return true;
	return false;
}

signed main()
{
	n = read(),m = read(),hp = read();
	int r = 0;
	for(register int i = 1;i <= n;++ i)
		f[i] = read(),r = max(r,f[i]);
	for(register int i = 1;i <= m;++ i)
	{
		int x = read(),y = read(),z = read();
		add(x,y,z);
		add(y,x,z);
	}
	int qwq = r;
	r ++;
	int l = 0;
	while(l < r)
	{
		int mid = (r + l) >> 1;
		if(check(mid))r = mid;
		else	l = mid + 1;
	}
	if(l == qwq + 1)
	{
		cout << "AFK" << endl;
		return 0;
	}
	cout << l << endl;
	return 0;
}

为什么最后两个点WA?

回复可回关