GYM 101933D（最短路、二分、dp）

要点

非要先来后到暗示多源最短路，求最小的最大值暗示二分
二分内部的check是关键，dp处理一下，\(dp[i]\)表示第\(i\)笔订单最早何时送达，如果在ddl之前到不了则\(return\ 0\)。我觉得其中\(time\)变量的维护很好地使复杂度降了一维。
第一发WA点：算法看了一遍感觉没有可改的，就把二分的\(r\)调大了，又把\(longlong\)的输入输出改为流，莽试一发就过了……

#include <cstdio>

#include <iostream>

#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 1005, maxm = 5005;

const ll INF = 1e18;

int n, m, k;

ll s[maxn], u[maxn], t[maxn];

struct Edge {

	int to, nxt, cost;

}e[maxm << 1];

int head[maxn], tot;

ll dis[maxn][maxn];

void add(int u, int v, int c) {

	e[++tot].to = v, e[tot].cost = c, e[tot].nxt = head[u], head[u] = tot;

}

void dij(int st) {

	for (int i = 1; i <= n; i++)	dis[st][i] = INF;

	dis[st][st] = 0;

	typedef pair<ll, int> pli;

	priority_queue<pli, vector<pli>, greater<pli>> Q;

	Q.push({0, st});

	while (Q.size()) {

		ll d = Q.top().first;

		int p = Q.top().second;

		Q.pop();

		if (d > dis[st][p])	continue;

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

			int t = e[i].to;

			if (dis[st][t] > d + e[i].cost) {

				dis[st][t] = d + e[i].cost;

				Q.push({dis[st][t], t});

			}

		}

	}

}

bool ok(ll D) {

	ll dp[maxn];

	dp[0] = 0;

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

		dp[i] = INF;

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

		ll val = dis[1][u[i]];

		ll st = max(t[i], dp[i - 1] + dis[u[i - 1]][1]);

		dp[i] = min(dp[i], st + val);

		if (dp[i] > s[i] + D)	return 0;

		ll time = s[i] + D - st - val;

		if (time < 0)	continue;

		for (int j = i + 1; j <= k; j++) {

			val += dis[u[j - 1]][u[j]];

			if (t[j] > st) {

				time -= t[j] - st;

				st = t[j];

			}

			time = min(time, s[j] + D - st - val);

			if (time < 0)	break;

			dp[j] = min(dp[j], st + val);

		}

	}

	return 1;

}

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1, u, v, c; i <= m; i++) {

		scanf("%d %d %d", &u, &v, &c);

		add(u, v, c), add(v, u, c);

	}

	scanf("%d", &k);

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

		cin >> s[i] >> u[i] >> t[i];

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

		dij(i);

	}

	ll l = 0, r = 1e18, ans;

	while (l <= r) {

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

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

		else	l = mid + 1;

	}

	cout << ans << '\n';

	return 0;

}

巴特西

GYM 101933D（最短路、二分、dp）

要点

最新文章

热门文章