自动搬运

查看原文

来自洛谷，原作者为

	chzhc 天天开心！

搬运于2025-08-24 21:30:37，当前版本为作者最后更新于2021-08-08 20:44:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

如果 $b, e, c$ 开到 1e9 题解中的做法会 TLE

实际上有 $\mathcal O(m \times (n+m) \log m)$ 的做法。

若存在一条路使得在每一条马路上时间都没有卡在时间上限，那么至少可以在 $s$ 路口多停留一个单位时间。依此类推，最优答案必然走过一条刚好卡在时间上限的马路。那么我们枚举这条马路，从这条马路的两个路口分别出发(提前建好反向边)走到 $s$ 和 $t$，最后统计答案即可。

所以枚举每条边跑 dij / spfa 就行了

code

#include <bits/stdc++.h>
using namespace std;
int n, m, beg, end, x, y, xx, yy, z, ans = 707406378;
int disa[1000001], disb[1000001], team[1000001], teamb[1000001];
int tot, next[1000001], first[1000001], front[1000001], 
	go[1000001], ta[1000001], tb[1000001], value[1000001];
int totb, nextb[1000001], firstb[1000001], frontb[1000001], 
	gob[1000001], tab[1000001], tbb[1000001], valueb[1000001];
void Add(int x, int y, int xx, int yy, int z)
{
	next[++tot] = first[x];
	first[x] = tot;
	front[tot] = x;
	go[tot] = y;
	ta[tot] = xx;
	tb[tot] = yy;
	value[tot] = z;
}
void Addd(int x, int y, int xx, int yy, int z)
{
	nextb[++totb] = firstb[x];
	firstb[x] = totb;
	frontb[totb] = x;
	gob[totb] = y;
	tab[totb] = xx;
	tbb[totb] = yy;
	valueb[totb] = z;
}
void SpfaOne(int x, int ti)
{
	int t = 0, w = 1;
	team[w] = x;
	disa[x] = 0;
	while (t < w)
	{
		int u = team[++t];
		for (int i = first[u]; i; i = next[i])
		{
			int v = go[i];
			if (disa[u] + ti + value[i] <= tb[i])
			{
				if (disa[u] + ti < ta[i])
				{
					if (disa[v] > ta[i] + value[i] - ti)
					{
						disa[v] = ta[i] + value[i] - ti;
						team[++w] = v;
					}
				}
				else if (disa[v] > disa[u] + value[i])
				{
					disa[v] = disa[u] + value[i];
					team[++w] = v;
				}
			}
		}
	}
}
void SpfaTwo(int x, int ti)
{
	int t = 0, w = 1;
	teamb[w] = x;
	disb[x] = 0;
	while (t < w)
	{
		int u = teamb[++t];
		for (int i = firstb[u]; i; i = nextb[i])
		{
			int v = gob[i];
			if (ti - disb[u] - valueb[i] >= tab[i])
			{
				if (ti - disb[u] > tbb[i])
				{
					if (disb[v] > ti - tbb[i] + valueb[i])
					{
						disb[v] = ti - tbb[i] + valueb[i];
						teamb[++w] = v;
					}
				}
				else if (disb[v] > disb[u] + valueb[i])
				{
					disb[v] = disb[u] + valueb[i];
					teamb[++w] = v;
				}
			}
		}
	}
}
int main()
{
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	scanf("%d%d%d%d", &n, &m, &beg, &end);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d%d%d%", &x, &y, &xx, &yy, &z);
		if (z <= yy - xx) // 若开放的时间都不够通过则不需要这一条边 
		{
			Add(x, y, xx, yy, z);
			Addd(y, x, xx, yy, z);// 反向边
		}
	}
	for (int i = 1; i <= tot; ++i)
	{
		for (int j = 1; j <= n; ++j) disa[j] = disb[j] = 707406378;
		SpfaOne(go[i], tb[i]);// 跑到终点
		SpfaTwo(front[i], tb[i] - value[i]); // 跑到起点
		if (ans > disa[end] + disb[beg] + value[i]) // 更新最小值
			ans = disa[end] + disb[beg] + value[i];
	}
	if (ans < 707406378)
		printf("%d", ans);
	else printf("Impossible"); // 无解
	fclose(stdin), fclose(stdout);
}