洛谷1462(重题1951) 通往奥格瑞玛的道路(收费站_NOI导刊2009提高(2))

1462原题链接

1951原题链接

显然答案有单调性，所以可以二分答案，用\(SPFA\)或\(dijkstra\)跑最短路来判断是否可行即可。

注意起点也要收费，\(1462\)数据较水，我一开始没判也过了，但重题\(1951\)把我卡掉了。。

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N = 1e4 + 10;

const int M = 1e5 + 10;

struct dd {

	int x, D;

	bool operator < (const dd &b) const { return D > b.D; }

};

int fi[N], di[M], ne[M], da[M], dis[N], MI[N], f[N], l, n, HP, st, ed;

bool v[N];

priority_queue<dd>q;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y, int z)

{

	di[++l] = y;

	da[l] = z;

	ne[l] = fi[x];

	fi[x] = l;

}

inline int maxn(int x, int y){ return x > y ? x : y; }

inline int minn(int x, int y){ return x < y ? x : y; }

bool dij(int V)

{

	if (f[st] > V)

		return false;

	int i, x, y;

	memset(dis, 60, sizeof(dis));

	memset(v, 0, sizeof(v));

	dis[st] = 0;

	q.push((dd){st, 0});

	while (!q.empty())

	{

		x = q.top().x;

		q.pop();

		if (v[x])

			continue;

		v[x] = 1;

		for (i = fi[x]; i; i = ne[i])

			if (dis[y = di[i]] > dis[x] + da[i] && f[di[i]] <= V)

				q.push((dd){y, dis[y] = dis[x] + da[i]});

	}

	return dis[ed] < HP;

}

int main()

{

	int i, m, x, y, z, l = 1e9, r = 0, mid;

	n = re();

	m = re();

	st = re();

	ed = re();

	HP = re();

	for (i = 1; i <= n; i++)

	{

		f[i] = re();

		l = minn(l, f[i]);

		r = maxn(r, f[i]);

	}

	for (i = 1; i <= m; i++)

	{

		x = re();

		y = re();

		z = re();

		add(x, y, z);

		add(y, x, z);

	}

	if (!dij(1e9))

	{

		printf("-1");

		return 0;

	}

	while (l < r)

	{

		mid = (l + r) >> 1;

		dij(mid) ? r = mid : l = mid + 1;

	}

	printf("%d", r);

	return 0;

}