[数据结构与算法]P1462 通往奥格瑞玛的道路(二分+dijkstra)

P1462?通往奥格瑞玛的道路https://www.luogu.com.cn/problem/P1462

?一道很不错的题，考察了二分和最短路

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_map>
#include <cmath>
#include <map>
#include <cctype>
#include <cstdlib>
#include <deque>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))


int n, m, b;
int head[MAXN];
int nxt[MAXN];
int cost[MAXN];
int ver[MAXN];
int s[MAXN];
int cnt;
int d[MAXN];
inline void add(int x, int y, int c) {
	ver[++cnt] = y;
	cost[cnt] = c;
	nxt[cnt] = head[x];
	head[x] = cnt;
}
bool vis[MAXN];
typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<P> > que;

bool judge(int mid) {
	if (mid < s[1])
		return true;
	for (int i = 1; i <= n; i++) {
		d[i] = INF;
		vis[i] = false;
	}
	d[1] = 0;
	que.push(P(0, 1));
	while (!que.empty()) {
		P t = que.top();
		que.pop();
		if (vis[t.second])
			continue;
		vis[t.second] = true;
		for (int i = head[t.second]; i; i = nxt[i]) {
			int v = ver[i];
			int c = cost[i];
			if (d[v] > c + d[t.second] && s[v] <= mid) {
				d[v] = d[t.second] + c;
				que.push(P(d[v], v));
			}
		}
	}
	//printf("%d", d[n]);
	if (d[n] > b)
		return true;
	else
		return false;
}


int main() {
	int x, y, c;
	int l = 0, r = 0;
	scanf("%d %d %d", &n, &m, &b);
	for (int i = 1; i <= n; i++)
		scanf("%d", s + i), r = max(r, s[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &c);
		if (x == y)
			continue;
		add(x, y, c);
		add(y, x, c);
	}
	if (judge(r)) {
		printf("AFK");
		return 0;
	}
	
	while (l <= r) {
		int mid = l + r >> 1;
		if (judge(mid))
			l = mid + 1;
		else
			r = mid - 1;
	}
	printf("%d", l);
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖