P1266 速度限制 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

亿眼分层图。

分层图除此之外还有很多应用（如给你一个图，求使任意（不多于） k 条边权值变为 0 后的 S 到 T 的最短路（ k 不大））。

最开始一直脑抽，认为如果当前速度小于到达的路的限速的话，仍然按照当前速度前进，就死活过不了样例。

我佛了。。

---

这里的分层图只是借用了一种表示不同状态的思想，而不是真的将图分层并在层之间建边跑最短路。

你大也可以将这试为动态规划的一种转移方式。

对于图 \(G=(V(G),E(G))\)，设 \(dis[i][j]\) 表示源点 S 到当前点 i，且到达速度为 j 时所花费的最短时间。

显然有 \(dis[i][j] = \min_{l=0}^{maxspeed_k}dis[k][l] + len(k,i) / speed(k \in E)\)。

所以 dijkstrar 内的松弛操作应写为：

• 这里用邻接表存图
• sp[i] 表示第 i 条边的速度限制（无限制为 0 ）
• len[i] 表示第 i 条边的长度
• u 是一个 pair<int, int> 的二元组，first 里存储点标号，second 里存储当前速度。
• \(from[i][j]\) 二元组则表示从 S 到第 i 号点，到达速度为 j 时的最短路径上前一个点的标号及前一个点的到达速度。

for(int i = first[u.first]; i; i = Next[i])
{
    int v = to[i], sped = (sp[i] ? sp[i] : u.second);
    double time = (double)len[i] / (double)sped;
    if(dis[u.first][u.second] + time < dis[v][sped])
    {
        dis[v][sped] = dis[u.first][u.second] + time;
        from[v][sped] = u;
        q.push(make_pair(-dis[v][sped], make_pair(v, sped)));
    }
}

最后我们只需要枚举终点的到达速度，取最大值，再依序输出路径即可。

Code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int n, m, d;
int first[N], Next[N], to[N], sp[N], len[N], tot;
double dis[205][1005];
int vis[205][1005];
pair<int, int> from[205][1005];
void add(int x, int y, int z, int zz)
{
	Next[++tot] = first[x];
	first[x] = tot;
	to[tot] = y;
	sp[tot] = z;
	len[tot] = zz;
	return;
}
void dijkstrar(int x)
{
	priority_queue<pair<double, pair<int, int> > > q;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= 505; j++)
		{
			dis[i][j] = 1e9;
			vis[i][j] = 0;
		}
	}
	dis[x][70] = 0;
	q.push(make_pair(0, make_pair(x, 70)));
	while(!q.empty())
	{
		pair<int, int> u = q.top().second;
		q.pop();
		if(vis[u.first][u.second])
		{
			continue;
		}
		vis[u.first][u.second] = 1;
		for(int i = first[u.first]; i; i = Next[i])
		{
			int v = to[i], sped = (sp[i] ? sp[i] : u.second);
			double time = (double)len[i] / (double)sped;
			if(dis[u.first][u.second] + time < dis[v][sped])
			{
				dis[v][sped] = dis[u.first][u.second] + time;
				from[v][sped] = u;
				q.push(make_pair(-dis[v][sped], make_pair(v, sped)));
			}
		}
	}
	return;
}
void write(int x, int v)
{
	if(x == 1)
	{
		printf("0 ");
		return;
	}
	write(from[x][v].first, from[x][v].second);
	printf("%d ", x - 1);
	return;
}
signed main()
{
	scanf("%d%d%d", &n, &m, &d);
	int x, y, z, zz;
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d%d%d", &x, &y, &z, &zz);
		x++;
		y++;
		add(x, y, z, zz);
	}
	dijkstrar(1);
	d++;
	int maxx = 0;
	dis[d][maxx] = 1e9;
	for(int i = 1; i <= 500; i++)
	{
		if(dis[d][i] < dis[d][maxx])
		{
			maxx = i;
		}
	}
	write(d, maxx);
	return 0;
}