rt

SPFA 90:提交记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, b, h[10010], f[10010], d[10010], ver[N], nxt[N], edge[N], tot, l, r, ans = -1;
bool v[10010];

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

bool SPFA(int k)
{
	if(f[1] > k)return false;
	queue<int> q;
	for(int i = 1; i <= n; ++ i ) d[i] = 1e16;
	memset(v, 0, sizeof(v));
	d[1] = 0;
	v[1] = 1;
	q.push(1);
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		v[x] = 0;
		for(int i = h[x]; i; i = nxt[i])
		{
			int y = ver[i], z = edge[i];
			if(f[y] > k) continue;
			if(d[y] > d[x] + z)
			{
				d[y] = d[x] + z;
				if(!v[y]) q.push(y), v[y] = 1;
			}
			if(y == n)
			{
				if(d[y] <= b) return true;
				return false;
			}
		}
	}
	return false;
}

inline int read()
{
	int x = 0;
	bool f = true;
	char ch = getchar();
	while(!isdigit(ch)){if(ch == '-') f = false; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? x : ~x + 1;
}

signed main() {
	n = read(), m = read(), b = read();
	for(int i = 1; i <= n; ++ i )
	{
		f[i] = read();
		l = min(l, f[i]);
		r = max(r, f[i]);
	}
	for(int i = 1; i <= m; ++ i )
	{
		int u, v, w;
		u = read(), v = read(), w = read();
		add(u, v, w);
	}
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(SPFA(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	if(ans == -1) puts("AFK");
	else printf("%lld", ans);
	return 0;
} 

dijkstra 100:提交记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, b, h[10010], f[10010], d[10010], ver[N], nxt[N], edge[N], tot, l, r, ans = -1;
bool v[10010];

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

bool dijkstra(int k)
{
	if(f[1] > k)return false;
	priority_queue<pair<int, int> > q;
	memset(d, 0x3f, sizeof(d));
	memset(v, 0, sizeof(v));
	d[1] = 0;
	q.push(make_pair(0, 1));
	while(!q.empty())
	{
		int x = q.top().second;
		q.pop();
		if(v[x])continue;
		v[x] = 1;
		for(int i = h[x]; i; i = nxt[i])
		{
			int y = ver[i], z = edge[i];
			if(f[y] > k) continue;
			if(d[y] > d[x] + z)
			{
				d[y] = d[x] + z;
				q.push(make_pair(-d[y], y));
			}
			if(y == n)
			{
				if(d[y] <= b) return true;
				return false;
			}
		}
	}
	return false;
}

inline int read()
{
	int x = 0;
	bool f = true;
	char ch = getchar();
	while(!isdigit(ch)){if(ch == '-') f = false; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? x : ~x + 1;
}

signed main() {
	n = read(), m = read(), b = read();
	for(int i = 1; i <= n; ++ i )
	{
		f[i] = read();
		l = min(l, f[i]);
		r = max(r, f[i]);
	}
	for(int i = 1; i <= m; ++ i )
	{
		int u, v, w;
		u = read(), v = read(), w = read();
		add(u, v, w);
	}
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(dijkstra(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	if(ans == -1) puts("AFK");
	else printf("%lld", ans);
	return 0;
}