Solution - TH3 SH4DY GR3Y - 洛谷保存站

- 出题人题解，写于出题后两个月。  
  不知道出题的时候发了什么电弄出来了这道题。可能是水电吧。
- 但说实话[黯洃銫](https://backrooms-wiki-cn.wikidot.com/th3-sh4dy-gr3y)这篇文真的好看。
- 本题数据很水，但是懒得动了。

---

其实是一个很显然的分层图最短路。观察到 $1 \le d \le 10$，于是分层。

分完层以后正常跑最短路。注意如果隧道过世了或者爬到一半的时候将要过世，那么开始时间顺延到隧道复活时。层间就不用管了。

答案是 $\max_{0 \le i \le d}\{\text{dis}_{n, i}\}$。

```cpp
#include <bits/stdc++.h>
#define rint register int
#define rllong register long long
#define llong long long
#define N 100005
#define M 1000006 
using namespace std;

#define Node tuple<llong, int, int>
priority_queue<Node, vector<Node>, greater<Node>> pq;
llong dis[N][15], vis[N][15];
llong to[M<<1], l[M<<1], s[M<<1], nxt[M<<1], head[N], gsiz;
#define mkarc(u,v,w1,w2) (++gsiz,to[gsiz]=v,l[gsiz]=w1,s[gsiz]=w2,nxt[gsiz]=head[u],head[u]=gsiz) 
int n, m, d;

int main(){
	scanf("%d %d %d", &n, &m, &d);
	for(rint i = 1; i <= m; ++i){
		rint u, v, w1, w2;
		scanf("%d %d %d %d", &u, &v, &w1, &w2);
		mkarc(u, v, w1, w2), mkarc(v, u, w1, w2);
	}
	for(rint i = 1; i <= n; ++i)
		for(rint j = 0; j <= d; ++j)
			dis[i][j] = 1e18+3;
    dis[1][0] = 0;
	pq.push(make_tuple(0, 1, 0));
	while(!pq.empty()){
		Node now = pq.top(); pq.pop();
		rint u = get<1>(now), k = get<2>(now);
        rllong w = dis[u][k];
		if(vis[u][k]) continue;
		vis[u][k] = true;
		for(rint i = head[u]; i; i = nxt[i]){
			rint v = to[i];
			if(k+1 <= d && !vis[v][k+1] && w+(l[i]<<1) < dis[v][k+1]){
				dis[v][k+1] = w+(l[i]<<1);
				pq.push(make_tuple(dis[v][k+1], v, k+1));
			}
			if(!vis[v][k] && ((w/s[i]%2 == 0 && (w+l[i])/s[i]%2 == 0) ? w+l[i] : (w/(2*s[i])+1)*2*s[i]+l[i]) < dis[v][k]){
				dis[v][k] =  ((w/s[i]%2 == 0 && (w+l[i])/s[i]%2 == 0) ? w+l[i] : (w/(2*s[i])+1)*2*s[i]+l[i]);
				pq.push(make_tuple(dis[v][k], v, k));
			}
		}
	}
	rllong ans = 1e18+3;
	for(rint i = 0; i <= d; ++i)
		ans = min(ans, dis[n][i]);
	if(ans >= 1e18) puts("th3-sh4dy-gr3y");
	else            printf("%lld", ans);
	return 0;
}

```

---

顺便说一下配置部分分的理由。

- $n \le 10, m \le 10$：给打暴力的人。
- $n \le 10^3, m \le 10^4$：给 [yuruilin2026](https://www.luogu.com.cn/user/1294410) 搞出来的一种神奇 $\mathcal{O}(nm)$ 做法。
- $d = 0$：给想不出来分层图的人。
- 正常数据范围：给正解。

正在渲染内容...