题解【洛谷P1948】[USACO08JAN]电话线Telephone Lines

题面

题解

很显然，答案满足单调性。

因此，可以使用二分答案求解。

考虑\(check\)的实现。

贪心地想，免费的\(k\)对电话线一定都要用上。

每次\(check\)时将小于\(mid\)的边权设为\(0\)，其它的设为\(1\)。

跑一边最短路判断\(\mathrm{dist[n]}\)是否\(\leq k\)即可。

代码

#include <bits/stdc++.h>

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 10003;

int n, p, k, dist[maxn], vis[maxn];

vector <int> v[maxn], edge[maxn], f[maxn];

inline bool check(int x)

{

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

	{

		int len = f[i].size();

		for (int j = 0; j < len; j+=1)

		{

			if (f[i][j] <= x) edge[i][j] = 0;

			else edge[i][j] = 1;

		}

	}//重设边权

	queue <int> q;

	memset(dist, 0x3f, sizeof(dist));

	memset(vis, 0, sizeof(vis));

	vis[1] = 1;

	dist[1] = 0;

	q.push(1);

   	while (!q.empty())

   	{

		int u = q.front(); q.pop();

		vis[u] = 0;

		int len = v[u].size();

		for (int i = 0; i < len; i+=1)

		{

			int vv = v[u][i], w = edge[u][i];

			if (dist[vv] > dist[u] + w)

			{

				dist[vv] = dist[u] + w;

				if (!vis[vv]) q.push(vv);

			}

		}

   	}

	return dist[n] <= k;

}

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi(), p = gi(), k = gi();

	for (int i = 1; i <= p; i+=1)

	{

		int u = gi(), vv = gi(), w = gi();

		v[u].push_back(vv);

		v[vv].push_back(u);

		edge[u].push_back(w);

		edge[vv].push_back(w);//现边权

		f[u].push_back(w);

		f[vv].push_back(w);//原边权

	}

	int l = 0, r = 1000000000, ans = -1;

	while (l <= r)

	{

		int mid = (l + r) >> 1;

		if (check(mid)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	printf("%d\n", ans);

	return 0;

}