蓝桥杯历届试题|第十一届蓝桥杯 ——限高杆拆点|最短路径

题目描述
某市有 n 个路口，有 m 段道路连接这些路口，组成了该市的公路系统。
其中一段道路两端一定连接两个不同的路口，道路中间不会穿过路口。
由于各种原因，在一部分道路的中间设置了一些限高杆，有限高杆的路段货车无法通过。
在该市有两个重要的市场 A 和 B，分别在路口 1 和 n 附近，
货车从市场 A 出发，首先走到路口 1，然后经过公路系统走到路口 n，才能到达市场 B。
两个市场非常繁华，每天有很多货车往返于两个市场之间。
市长发现，由于限高杆很多，导致货车可能需要绕行才能往返于市场之间，
【蓝桥杯历届试题|第十一届蓝桥杯 ——限高杆】这使得货车在公路系统中的行驶路程变长，增加了对公路系统的损耗，增加了能源的消耗，同时还增加了环境污染。
市长决定要将两段道路中的限高杆拆除，使得市场 A 和市场 B 之间的路程变短，请问最多能减少多长的距离？
输入格式
输入的第一行包含两个整数 n, m，分别表示路口的数量和道路的段数。
接下来 m 行，每行四个整数 a, b, c, d，表示路口 a 和路口 b 之间有一段长度为 c 的道路。

如果 d 为 0，表示这段道路上没有限高杆；
如果 d 为 1，表示这段道路上有限高杆。

两个路口之间可能有多段道路。
输入数据保证在不拆除限高杆的情况下，货车能通过公路系统从路口 1 正常行驶到路口 n。
输出格式
输出一行，包含一个整数，表示拆除两段道路的限高杆后，市场 A 和市场 B 之间的路程最大减少多长距离。
输入样例
5 7
1 2 1 0
2 3 2 1
1 3 9 0
5 3 8 0
4 3 5 1
4 3 9 0
4 5 4 0
输出样例
6
样例解释
只有两段道路有限高杆，全部拆除后，1 到 n 的路程由原来的 17 变为了 11，减少了 6。
数据范围
对于 30% 的评测样例， 2 ≤ n ≤ 10 ， 1 ≤ m ≤ 20 , 1 ≤ c ≤ 100 2≤n≤10，1≤m≤20,1≤c≤100 2≤n≤10，1≤m≤20,1≤c≤100
对于 50% 的评测样例， 2 ≤ n ≤ 100 ， 1 ≤ m ≤ 1000 , 1 ≤ c ≤ 1000 2≤n≤100，1≤m≤1000,1≤c≤1000 2≤n≤100，1≤m≤1000,1≤c≤1000
对于 70% 的评测样例， 2 ≤ n ≤ 1000 ， 1 ≤ m ≤ 10000 , 1 ≤ c ≤ 10000 2≤n≤1000，1≤m≤10000,1≤c≤10000 2≤n≤1000，1≤m≤10000,1≤c≤10000
对于所有评测样例， 2 ≤ n ≤ 10000 ， 2 ≤ m ≤ 100000 , 1 ≤ c ≤ 10000 2≤n≤10000，2≤m≤100000,1≤c≤10000 2≤n≤10000，2≤m≤100000,1≤c≤10000，至少有两段道路有限高杆。
题解一（超时）
枚举 && SPFA：可得 30% ~ 50%的分数

#include #include #include #include using namespace std; const int N = 10010, M = 200010; int n, m; bool st[N]; int dist[N]; int h[N], e[M], w[M], s[M], ne[M], idx; int p[M][2]; void add(int a, int b, int c, int d) { e[idx] = b, w[idx] = c, s[idx] = d, ne[idx] = h[a], h[a] = idx ++; }int spfa() { queue q; memset(dist, 0x3f, sizeof dist); q.push(1); dist[1] = 0; st[1] = true; while(q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { if(s[i]) continue; int j = e[i]; if(dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if(!st[j]) { st[j] = true; q.push(j); } } } }return dist[n]; }int main() { cin >> n >> m; int k = 0; memset(h, -1, sizeof h); while(m --) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); if(d) p[k][0] = idx, p[k ++][1] = idx + 1; // 记录有限高杆的道路 add(a, b, c, d), add(b, a, c, d); }int maxv = spfa(); int minv = maxv; for (int i = 0; i < k; i ++)// 枚举要拆除的两根限高杆 for (int j = i + 1; j < k; j ++) { s[p[i][0]] = s[p[i][1]] = 0; s[p[j][0]] = s[p[j][1]] = 0; minv = min(minv, spfa()); s[p[i][0]] = s[p[i][1]] = 1; s[p[j][0]] = s[p[j][1]] = 1; }cout << maxv - minv << endl; return 0; }

题解二
SPFA（拆点）：
dist[n][k]：从 1 号点走到 n 号点，且经过的限高杆数量为 k 的最短距离；

#include #include #include #include using namespace std; typedef pair PII; const int N = 10010, M = 200010; int n, m; bool st[N][3]; int dist[N][3]; int h[N], e[M], s[M], w[M], ne[M], idx; void add(int a, int b, int c, int d) { e[idx] = b, w[idx] = c, s[idx] = d, ne[idx] = h[a], h[a] = idx ++; }void spfa() { queue q; memset(dist, 0x3f, sizeof dist); q.push({1, 0}); dist[1][0] = dist[1][1] = dist[1][2] = 0; st[1][0] = true; while(q.size()) { int u = q.front().first; int pole = q.front().second; q.pop(); st[u][pole] = false; for (int i = h[u]; i != -1; i = ne[i]) { int v = e[i]; int total = pole + s[i]; if(total > 2) continue; if(dist[v][total] > dist[u][pole] + w[i]) { dist[v][total] = dist[u][pole] + w[i]; if(!st[v][total]) { st[v][total] = true; q.push({v, total}); } } } } }int main() { cin >> n >> m; memset(h, -1, sizeof h); while(m --) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); add(a, b, c, d), add(b, a, c, d); }spfa(); cout << dist[n][0] - min(dist[n][1], dist[n][2]) << endl; return 0; }

蓝桥杯C/C++组省赛历年题