迪杰斯特拉+二分+优先队列+拓扑+堆优化（奶牛航线Cowroute、架设电话线dd、路障Roadblocks、奶牛交通Traffic）

原文地址

https://fmcraft.top/index.php/Programming/2025040402.html

主要算法

迪杰斯特拉Dijkstra

题目列表

P1：奶牛航线Cowroute

题目描述

题目描述
Bessie已经厌倦了农场冬天的寒冷气候，她决定坐飞机去更温暖的地方去度假。不幸的是，她发现只有Air Bovinia这一家航空公司愿意卖飞机票给牛，而且这家航空公司的飞机票的结构有些复杂。
Air Bovinia有N架飞机用来运营(1 <= N <= 1000)，每架飞机都只飞一条由两个或者更多城市组成的特定航线。举个例子，一架飞机的航线由1号城市开始，随后飞去5号城市，接着飞去2号城市，最后到达8号城市。同一条航线中，同一座城市不会出现两次。如果Bessie决定选择乘坐一条航线，她可以在航线的任意城市登机，然后在这条航线后续的任意一个城市下飞机。每条航线都有一个确定的价格，Bessie如果乘坐了一条航线就必须支付全款，即使她只乘坐了这条航线的一小部分。如果Bessie乘坐了同一条航线多次，她每次都需要支付航线所需的费用。
Bessie想要找到从农夫John的农场(城市A)到她的目的地(城市B)的最便宜的飞行路线。请帮她计算出她最少需要多少钱，同时也请计算出她在花费最少的前提下，经过的城市的最少数量。
输入
输入的第一行包括三个用空格分离的整数A、B和N。表示出发和目的地城市的编号，和总的航班数。
接下来2N行描述航线信息。
每两行第一行的两个整数分别表示使用这条航线所需要的花费(范围为区间1…1,000,000,000)。和航线所经过的城市数(范围为区间1…100)。
第二行包含一个城市列表，依次表示航线沿途经过的城市(城市标号的范围为1…1000)。
请注意，花费总和很容易就会超过32位整型。
输出
输出两个以空格分离的整数，分别为从城市A到城市B所需要的最小花费，和在此前提下所需要经过城市的最少数量。m
如果无解，那么输出"-1 -1“。(引号不用输出)
样例输入 复制

3 4 3
3 5
1 2 3 4 5
2 3
3 5 4
1 2
1 5

样例输出 复制

2 2

提示
样例说明
坐第2个航班，花费为2，经过5、4两个城市

题解报告

本题存在错误，输出样例的第二个存在错误，所以标准程序中不输出第二个答案
一、题目分析
Bessie 要从城市 A 前往城市 B 度假，Air Bovinia 航空公司有 N 条航线，每条航线由两个或更多城市组成，同一航线中城市不会重复。Bessie 可以在航线的任意城市登机，在后续任意城市下机，且乘坐航线需支付全款，多次乘坐同航线需多次付费。我们的任务是帮 Bessie 找到从城市 A 到城市 B 的最便宜飞行路线，并计算在花费最少的前提下经过的最少城市数量，若无法到达则输出 “-1 -1”。
二、算法思路
构建图模型：
对于每条航线，将其拆分成多个边。例如，若航线经过城市 a1, a2, …, an，则构建边 (a1, a2), (a1, a3), …, (a1, an), (a2, a3), …, (a2, an), …, (an-1, an)，每条边的权重为该航线的费用。这样，我们就将航线信息转化为了图的邻接关系。
使用 Dijkstra 算法求解：
Dijkstra 算法是一种用于计算图中从一个源点到其他所有点的最短路径的算法。在本题中，我们将源点设为城市 A，目标点为城市 B。
初始化距离数组 d，将所有城市的距离设为无穷大，将源点 A 的距离设为 0。
初始化标记数组 fl，用于标记城市是否已被访问，初始时所有城市都未被访问。
循环 n 次（n 为城市总数），每次找到距离最小且未被访问的城市 fx。
遍历 fx 的所有邻接城市 sx，如果通过 fx 到达 sx 的距离比当前记录的 sx 的距离更小，则更新 sx 的距离。
标记 fx 为已访问。
处理输出：
若最终 d[B] 仍为无穷大，说明无法从城市 A 到达城市 B，输出 “-1 -1”；否则，输出 d[B] 作为最小花费。
为了得到最少城市数量，我们可以在 Dijkstra 算法过程中记录每个城市的前驱城市，最后从城市 B 回溯到城市 A 来计算经过的城市数量。但原代码中未实现这部分功能，仅计算了最小花费。

标准程序

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int A,B,n,i,j,k,x,y,mi,sx,fx,sg,a[N],d[N],fl[N];
vector <int> f[N],g[N];
signed main(){cin>>A>>B>>n;for(i=1;i<=n;i++){cin>>x>>y;for(j=1;j<=y;j++) cin>>a[j];for(j=1;j<y;j++) for(k=j+1;k<=y;k++)f[a[j]].push_back(a[k]),g[a[j]].push_back(x);}for(n=1000,i=1;i<=n;i++) d[i]=1e18,fl[i]=1;d[A]=0;for(i=1;i<=n;i++){mi=1e18;for(j=1;j<=n;j++) if(d[j]<mi&&fl[j]) fx=j,mi=d[j];for(j=0;j<f[fx].size();j++){sx=f[fx][j];sg=g[fx][j];if(sg+d[fx]<d[sx]) d[sx]=d[fx]+sg;}fl[fx]=0;}cout<<(d[B]==1e18?-1:d[B]);
}

P2：架设电话线dd

题目描述

题目描述
在郊区有 N座通信基站，P条双向电缆，第 i 条电缆连接基站 Ai和 Bi 。特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第 i条电缆需要花费 Li 。
电话公司正在举行优惠活动。农场主可以指定一条从 1号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。
一句话题意:在加权无向图上求出一条从 1 号结点到 N号结点的路径，使路径上第 K+1 大的边权尽量小。
输入
第一行三个整数 N,P,K;
接下来 PP 行，每行三个整数 Ai,Bi,Li.
输出
若不存在从 1到 N 的路径，输出 −1。否则输出所需最小费用。
样例输入 复制

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

样例输出 复制

4

提示
数据范围：
0≤K<N≤1000,1≤P≤2000

题解报告

本题的目标是在加权无向图上找到一条从 1 号结点到 N 号结点的路径，使得路径上第 K + 1 大的边权尽量小。我们采用二分答案的方法来解决这个问题。
二分的范围是边权的取值范围，这里边权的最小值可能为 0（虽然题目中未明确提及边权下限，但根据题意可合理推测），边权的最大值在数据范围给出的情况下最大为 1e9（因为后面代码中有 w = 1e9 的设置）。
对于二分得到的每一个可能的边权值 mid，我们通过一个基于优先队列的广度优先搜索（BFS）来判断是否存在一条从 1 号基站到 N 号基站的路径，使得路径上大于 mid 的边的数量不超过 k 条。如果存在这样的路径，说明当前的 mid 是一个可行解，我们可以继续缩小上界来寻找更小的可行解；如果不存在这样的路径，说明当前的 mid 太小，我们需要增大下界。
总体流程就是：
首先读取输入的节点数量 n、边的数量 m 和免费升级边的最大数量 k。
然后读取每条边的信息（连接的两个节点 x、y 和边的权值 z），并将边的信息存储在邻接表 f 和 g 中（f 存储节点的邻接关系，g 存储对应的边权）。
初始化二分的下界 t 为 0，上界 w 为 1e9，记录答案的变量 bao 为 -1（表示初始时没有找到可行解）。
进行二分查找，当 t 小于等于 w 时，计算中间值 mid。调用 pd(mid) 函数判断 mid 是否为可行解。如果是，则更新答案 bao 为 mid，并将上界 w 更新为 mid - 1；否则将下界 t 更新为 mid + 1。
最后输出答案 bao，如果最终 bao 仍然为 -1，则表示不存在从 1 到 N 的路径，输出 -1；否则输出 bao，即所需的最小费用。
对于判断函数：
该函数用于判断对于给定的边权值 x，是否存在一条从 1 号基站到 N 号基站的路径，使得路径上大于 x 的边的数量不超过 k 条。
首先，清空优先队列 q，并初始化距离数组 d 为一个很大的值（这里是 2e9），标记数组 fl 为 1（表示所有节点未被访问过）。
将 1 号节点的距离设为 0，并将其加入优先队列 q。
然后进入循环，从优先队列中取出距离最小的节点 fx 及其距离 fb。如果该节点已经被访问过（即 fl[fx] == 0），则跳过。
遍历节点 fx 的所有邻接节点 sx，计算 sg（如果邻接边的权值 g[fx][i] 大于 x，则 sg 为 1，否则为 0）。如果通过节点 fx 到达节点 sx 的距离（d[fx] + sg）小于原来记录的节点 sx 的距离 d[sx]，则更新 d[sx]，并将节点 sx 及其新的距离加入优先队列 q。
最后，判断 d[n] 是否小于等于 k，如果是，则说明存在满足条件的路径，返回 true；否则返回 false。

标准程序

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k,i,x,y,z,t,w,mid,bao,d[N],fl[N];
vector <int> f[N],g[N];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
bool pd(int x){int fx,fb,sx,sg;while(!q.empty()) q.pop();for(i=1;i<=n;i++) d[i]=2e9,fl[i]=1;d[1]=0;q.push(make_pair(0,1));while(!q.empty()){fx=q.top().second;fb=q.top().first;q.pop();if(fl[fx]==0) continue;for(fl[fx]=i=0;i<f[fx].size();i++){sx=f[fx][i];sg=(g[fx][i]>x);if(d[fx]+sg<d[sx]) d[sx]=d[fx]+sg,q.push(make_pair(d[sx],sx));}}return d[n]<=k;
}
int main(){cin>>n>>m>>k;for(i=1;i<=m;i++) cin>>x>>y>>z,f[x].push_back(y),f[y].push_back(x),g[x].push_back(z),g[y].push_back(z);t=0;w=1e9;bao=-1;while(t<=w){mid=(t+w)/2;if(pd(mid)) bao=mid,w=mid-1;else t=mid+1;}cout<<bao;
}

P3：路障Roadblocks

题目描述

题目描述
贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。
贝茜所在的乡村有 R(1≤R≤10^5) 条双向道路，每条路都连接了所有的 N(1≤N≤5000) 个农场中的某两个。贝茜居住在农场 1，她的朋友们居住在农场 NN（即贝茜每次旅行的目的地）。
贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且一条路可以重复走多次。当然第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
输入
第1行为两个整数，N和R，用空格隔开；
第 2…R+1行：每行包含三个用空格隔开的整数 A、B 和D，表示存在一条长度为 D(1≤D≤5000) 的路连接农场A和农场B。
输出
输出仅一个整数，表示从农场1到农场N的第二短路的长度。
样例输入 复制

4 4
1 2 100
2 4 200
2 3 250
3 4 100

样例输出 复制

450

提示
最短路：1→2→4（长度为 100+200=300）
第二短路：1→2→3→4（长度为4（长度为100+250+100=450$）

题解报告

本题的目标是找到从 1 号节点到 N 号节点的第二短路。我们可以使用 Dijkstra 算法的变形来解决这个问题。
步骤：
初始化距离数组 d1 和 d2，分别表示从 1 号节点到其他节点的最短距离和次短距离。将 d1 初始化为无穷大，d2 初始化为一个很大的值。
创建一个优先队列 q，用于存储节点及其到源节点的距离。将 1 号节点及其距离 0 加入优先队列 q。
进行 Dijkstra 算法的迭代过程，每次从优先队列中取出距离最小的节点 fx 及其距离 fy。
如果当前节点已经访问过，则跳过。
遍历当前节点的邻接节点，计算 sg（如果邻接边的权值 g[fx][i] 大于 x，则 sg 为 1，否则为 0）。
如果通过当前节点到达邻接节点的距离（fy + sg）小于 d1[sx]，则更新 d1[sx] 和 d2[sx]，并将邻接节点及其新的距离加入优先队列 q。
如果通过当前节点到达邻接节点的距离（fy + sg）小于 d2[sx]，则更新 d2[sx]，并将邻接节点及其新的距离加入优先队列 q。
最后，输出 d2[N]，即从 1 号节点到 N 号节点的第二短路的长度。

标准程序

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,i,j,x,y,z,fx,fy,lfb,sx,sg,d1[N],d2[N];
vector <int> f[N],g[N];
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main(){cin>>n>>m;for(i=1;i<=m;i++) cin>>x>>y>>z,f[x].push_back(y),f[y].push_back(x),g[x].push_back(z),g[y].push_back(z);for(i=1;i<=n;i++) d1[i]=d2[i]=2e9;d1[1]=0;q.push(make_pair(0,1));for(i=1;i<=5*n;i++){fx=q.top().second;fy=q.top().first;q.pop();for(j=0;j<f[fx].size();j++){sx=f[fx][j];sg=g[fx][j];x=fy+sg;if(x<d1[sx]) d2[sx]=d1[sx],d1[sx]=x;else if(x<d2[sx]) d2[sx]=x;q.push(make_pair(x,sx));}}cout<<d2[n];
}

P4：奶牛交通Traffic

题目描述

题目描述
农场中，由于奶牛数量的迅速增长，通往奶牛宿舍的道路也出现了严重的交通拥堵问题。约翰打算找出最忙碌的道路来重点整治。
这个牧区包括一个由M (1≤M≤50000)条单向道路组成的网络，以及N(1≤N≤5000)个交叉路口，每一条道路连接两个不同的交叉路口，奶牛宿舍位于第N个路口。每一条道路都由编号较小的路口通向编号较大的路口，这样就可以避免网络中出现环。显而易见所有道路都通向奶牛宿舍。而两个交叉路口可能由不止一条边连接。
在准备睡觉的时候，所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍。奶牛只会在入度为0的路口，且所有入度为0的路口都会有奶牛。
帮助约翰找出最忙碌的道路，即计算所有路径中通过某条道路的最大次数，答案保证可以用32位整数存储。
输入
第1行:两个用空格隔开的整数N和M.
第2…M+1行:每行两个用空格隔开的整数a，b，表示一条道路从a到b。
输出
一个整数，表示所有路径中通过某条道路的最大次数。
样例输入 复制

7 7
1 3
3 4
3 5
4 6
2 3
5 6

样例输出 复制

4

提示
输入说明:
通往奶牛宿舍的所有路径(1 3 4 6 7 )( 1 3 5 6 7 )( 2 3 4 6 7 )( 2 3 5 6 7 )。
输出说明:
以下是通往谷仓的四条可能路径：

1 3 4 6 7
1 3 5 6 7
2 3 4 6 7
2 3 5 6 7

题解报告

本题的目标是找到所有路径中通过某条道路的最大次数。我们可以使用拓扑排序和动态规划的方法来解决这个问题。
本题要求找出最忙碌的路段，即所有路径中通过某条道路的最大次数。我们可以使用拓扑排序来解决这个问题。
步骤：
初始化入度数组 join1 和 join2，分别表示每个节点的入度。
创建两个队列 q1 和 q2，用于存储入度为 0 的节点。
遍历所有节点，将入度为 0 的节点加入队列 q1。
进行拓扑排序的迭代过程，每次从队列 q1 中取出一个节点 fx，并将其加入队列 q2。
遍历当前节点的邻接节点，计算 sg（如果邻接边的权值 g[fx][i] 大于 x，则 sg 为 1，否则为 0）。
如果通过当前节点到达邻接节点的距离（fy + sg）小于 d1[sx]，则更新 d1[sx] 和 d2[sx]，并将邻接节点及其新的距离加入优先队列 q。
如果通过当前节点到达邻接节点的距离（fy + sg）小于 d2[sx]，则更新 d2[sx]，并将邻接节点及其新的距离加入优先队列 q。
最后，输出 d2[N]，即从 1 号节点到 N 号节点的第二短路的长度。

标准程序

#include <bits/stdc++.h>
using namespace std;
const int N=50010;
int i,j,n,m,x,y,fx,sx,ma,join1[N],join2[N],d1[N],d2[N];
vector <int> f[N],g[N];
queue <int> q;
int main(){cin>>n>>m;for(i=1;i<=m;i++) cin>>x>>y,f[x].push_back(y),join1[y]++,g[y].push_back(x),join2[x]++;for(i=1;i<=n;i++) if(join1[i]==0) q.push(i),d1[i]=1;while(!q.empty()){fx=q.front();q.pop();for(i=0;i<f[fx].size();i++){sx=f[fx][i];d1[sx]+=d1[fx];join1[sx]--;if(join1[sx]==0) q.push(sx);}}for(i=1;i<=n;i++) if(join2[i]==0) q.push(i),d2[i]=1;while(!q.empty()){fx=q.front();q.pop();for(i=0;i<g[fx].size();i++){sx=g[fx][i];d2[sx]+=d2[fx];join2[sx]--;if(join2[sx]==0) q.push(sx);}}for(i=1;i<=n;i++) for(j=0;j<f[i].size();j++)x=i,y=f[i][j],ma=max(ma,d1[x]*d2[y]);cout<<ma;
}

总结

通过以上四个问题的分析和解决，我们可以看到，图论中的最短路径问题在许多实际应用中都有广泛的应用。通过使用 Dijkstra 算法、拓扑排序和动态规划等方法，我们可以有效地解决这些问题。同时，这些问题的解决过程也让我们更加深入地理解了图论的基本概念和算法。
1. 最短路径问题：最短路径问题在计算机科学中，是指在给定图中，从一个起点到终点的最短路径问题。最短路径问题在很多实际应用中都得到了广泛的应用，如导航系统、网络优化、路径规划等。解决最短路径问题的关键是使用广度优先搜索（BFS）或深度优先搜索（DFS）算法，或者使用动态规划等方法。
2. 拓扑排序：拓扑排序是一种用于有向无环图（DAG）的排序算法。在拓扑排序中，我们将图中的节点按照它们之间的依赖关系进行排序。拓扑排序的应用非常广泛，如任务调度、依赖分析等。
3. 动态规划：动态规划是一种通过将问题分解为子问题，并利用子问题的解来求解原问题的方法。在最短路径问题中，我们可以使用动态规划来求解最短路径。动态规划的核心思想是将问题分解为子问题，并利用子问题的解来求解原问题。
4. 二分查找：二分查找是一种在有序数组中查找目标元素的算法。在最短路径问题中，我们可以使用二分查找来找到最短路径。二分查找的核心思想是将问题分解为子问题，并利用子问题的解来求解原问题。
5. 优先队列：优先队列是一种特殊的队列，它可以在 O(log n) 的时间复杂度内完成插入和删除操作。在解决最短路径问题时，我们可以使用优先队列来存储节点及其到源节点的距离，从而实现更高效的算法。