洛谷 [P1948] 电话线

二分答案

首先,最大值最小,就是二分答案

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN = 10005;

int head[MAXN], nume, n, m, k, l, r, mid, dis[MAXN];

bool f[MAXN];

struct edge {

	int to, nxt, dis;

}e[MAXN << 1];

void adde(int from, int to, int dis) {

	e[++nume].to = to;

	e[nume].nxt = head[from];

	e[nume].dis = dis;

	head[from] = nume;

}

queue <int> q;

bool chk(int x) {

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

	memset(f, 0, sizeof(f));

	dis[1] = 0;

	q.push(1);

	while(!q.empty()) {

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

		for(int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			int t = (e[i].dis > x);

			if(dis[v] > dis[u] + t) {

				dis[v] = dis[u] + t;

				q.push(v);

			}

		}

	}

	//cout << dis[n] << endl;

	return (dis[n] <= k);

}

int main() {

	cin >> n >> m >> k;

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

		int u, v, di;

		cin >> u >> v >> di;

		r = max(r, di);

		adde(u, v, di); adde(v, u, di);

	}

	int t = r;

	while(l <= r) {

		mid = (l + r) >> 1;

		//printf("%d %d %d\n", l, r, mid);

		if(chk(mid)) {

			r = mid - 1;

		}else l = mid + 1;

	}

	if(l <= t) cout << l << endl;

	else cout << -1 << endl;

	return 0;

}

还可以用 DP 的思路, 在SPFA中转移

也可以对于每种情况,建点连边,跑最短路

巴特西

洛谷 [P1948] 电话线

二分答案

最新文章

热门文章