自动搬运

查看原文

来自洛谷，原作者为

	H_Kaguya AFO

搬运于2025-08-24 22:45:35，当前版本为作者最后更新于2023-03-02 07:24:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛时想了想感觉没啥思路，结果最后写了一个麻烦的做法。

首先把下飞机之后的等待时间算到边权上，这就是一个普通的最短路了。
发现负边权最短路本身没啥好性质，所以考虑出发和到达时间固定这一点。

套路拆点。对于每个点，可能的到达 / 出发时间是有限的，我们就拆出来若干个点。
显然，可以在一个机场里等着，所以一个机场拆出来的点按时间顺序连一个链。
至于航班，就在相应的时间点之间连边。
这样，我们就把最短路问题转化成了连通性问题。跑一遍 BFS 即可。

由于边数是 $O(n)$ 级别的，所以最后出来的总点数也是 $O(n)$ 的。
由于需要按时间排序，所以总复杂度 $O(n\log n)$。
当然，可以把所有点放在一起基数排序，并且用单调指针代替二分查找来做到线性。实现就算了。

放上蒟蒻的赛时代码。

#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;
#define sz 200005
struct site
{
	int st, stim, ed, etim;
};
site dld[sz];
int n, m, top;
int wei[sz];
bool vis[sz << 1 | 1];
vector<int> tim[sz], ber[sz], fsl[sz << 1 | 1];
int read();
int haf(int, int);
void dfs(int);
int main()
{
	int x, y;
	n = read(); m = read();
	for (int i = 1; i <= m; ++i)
	{
		dld[i].st = read();
		dld[i].stim = read();
		dld[i].ed = read();
		dld[i].etim = read();
	}
	for (int i = 1; i <= n; ++i)
		wei[i] = read();
	for (int i = 1; i <= m; ++i)
	{
		tim[dld[i].st].emplace_back(dld[i].stim);
		tim[dld[i].ed].emplace_back(dld[i].etim + wei[dld[i].ed]);
	}
	for (int i = 1; i <= n; ++i)
		if (tim[i].size())
		{
			sort(tim[i].begin(), tim[i].end());
			x = 0;
			for (int j = 1; j < tim[i].size(); ++j)
				if (tim[i][j] != tim[i][x])
					tim[i][++x] = tim[i][j];
			tim[i].resize(x + 1);
			for (int j = 0; j <= x; ++j)
				ber[i].emplace_back(++top);
			for (int j = 1; j <= x; ++j)
				fsl[ber[i][j - 1]].emplace_back(ber[i][j]);
		}
	for (int i = 1; i <= m; ++i)
	{
		x = haf(dld[i].st, dld[i].stim);
		y = haf(dld[i].ed, dld[i].etim + wei[dld[i].ed]);
		fsl[x].emplace_back(y);
	}
	if (ber[1].size())
		dfs(1);
	puts("0");
	for (int i = 2; i <= n; ++i)
	{
		x = 1;
		for (int j = 0; j < ber[i].size(); ++j)
			if (vis[ber[i][j]])
			{
				printf ("%d\n", tim[i][j] - wei[i]);
				x = 0; break;
			}
		if (x)
			puts("-1");
	}
	return 0;
}

int read()
{
	int x = 0;
	char c = getchar();
	while (c < '0') c = getchar();
	do {
		x = x * 10 + (c & 15);
		c = getchar();
	}while (c >= '0');
	return x;
}

int haf(int a, int b)
{
	int lf = 0, rt = tim[a].size(), mid;
	while (rt > lf + 1)
	{
		mid = lf + rt >> 1;
		if (tim[a][mid] <= b)
			lf = mid;
		else
			rt = mid;
	}
	return ber[a][lf];
}

void dfs(int a)
{
	vis[a] = true;
	for (int i : fsl[a])
		if (!vis[i])
			dfs(i);
}