自动搬运

查看原文

来自洛谷，原作者为

	Lamb_Carp 那个男孩再也不能笑着说出下次一定

搬运于2025-08-24 22:41:49，当前版本为作者最后更新于2023-09-11 23:51:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意分析

在这个题中我们可以知道，如果这条路有限高杆的话，那么就不允许同行，但是如果没有则可以通行。

限高杆最多只可以拆两个。

有了这两个条件我们就可以从集合的角度进行分析（这样子可以保证不重不漏）：

• 首先，我们在面对一个杆的时候我们会有两种决策：

  1. 我当前拆卸的杆数还没有到达 2，那么我可以拆掉这个杆子并通行。

  2. 我不愿意拆这个杆子（不论我拆的数量是否到达 2），那么我就直接跳过，然后绕路走。

• 之后，如果我们面对的是一个没有杆子的道路：

  3. 我直接对这个最短路进行常规操作，正常更新。

分析到这里，大家大概也就明白，这是一个分层图的题，或者可以是一个动态规划 + 最短路的题目，具体做法看个人癖好。（我个人喜欢对分层图的题全部当成动态规划 + 最短路）。

最后需要留个心眼，比如说它拆了这条路的限高杆，但是这条路比其他路加起来还要长，这样子拆了还不如不拆，所以说，最后答案我们需要在这个拆一个和拆两个里面取最小值，然后我们再用一次也不拆的最小值减去这个最小值，就得到我们的正确答案了。

下面则是给那些自己敲了一遍，不断检查代码但是还是感觉是题目的问题（“多对的代码啊~可它就是不对~”） 的同学们的一些小帮助。

CODE TIME

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

const ll N = 1e4 + 10, M = 2e5 + 10;

ll n, m;

ll tot, ne[M], e[M], h[N], w[M], dis[N][3], sta[M];

bool st[N][3];

struct node
{
	ll id, dis, type;
	bool operator <(const node &x) const
	{
		return dis > x.dis;
	}
};

priority_queue<node> q;

inline void add(ll a, ll b, ll c, ll d)
{
	ne[++tot] = h[a], h[a] = tot, e[tot] = b, w[tot] = c, sta[tot] = d;
}

inline void dij(ll s)
{
	memset(dis, 0x3f, sizeof dis);
	memset(st, 0, sizeof st);
	
	dis[s][0] = dis[s][1] = dis[s][2] = 0;
	
	q.push({s, 0, 0});
	
	while(q.size())
	{
		node asd = q.top();
		q.pop();
		ll u = asd.id, t = asd.type, dist = asd.dis;
		if(st[u][t]) continue;
		st[u][t] = 1;
		for(rl i=h[u]; ~i; i = ne[i])
		{
			ll v = e[i];
			if(sta[i] && t <= 1)
			{
				if(dis[v][t + 1] > dis[u][t] + w[i])
				{
					dis[v][t + 1] = dis[u][t] + w[i];
					q.push({v, dis[v][t + 1], t + 1});
				}
				else continue;
			}else if(!sta[i]) 
			{
				if(dis[v][t] > dis[u][t] + w[i])
				{
					dis[v][t] = dis[u][t] + w[i];
					q.push({v, dis[v][t], t});
				}
			}
		}
	}
}

int main()
{
	memset(h, -1, sizeof h);
	
	cin >> n >> m;
	
	for(rl i=1; i <= m; ++ i)
	{
		ll a, b, c, d;
		cin >> a >> b >> c >> d;
		add(a, b, c, d), add(b, a, c, d);
	}
	
	dij(1);
	
	cout << dis[n][0] - min(dis[n][1], dis[n][2]) << endl;
	return 0;
}

完结撒花~感谢支持我的题解（高情商的人应该都懂我的意思）