算法学习系列（五十二）：单源最短路的建图方式

本文主要是介绍算法学习系列（五十二）：单源最短路的建图方式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

本来是一直学 $D P$ 着呢，不过我觉得 $D P$ 这种问题太难了，而且不太好做，而且考场上其实能做出来的不是很多，我觉得还是得难易结合，所以打算 $D P$ 和图论这两章一起学，一天学一个。然后今天先讲单源最短路的建图方式，还是以做题为主，然后开始吧。

一、热浪

标签：单源最短路

思路：关于最短路问题可以参考我之前的博客，然后因为自己准备的是蓝桥杯是 $O I$ 赛制的，所以还是要尽量在选择算法的时候要一步到位。首先这道题是单源最短路，且都是正权边，朴素版的 $D ijk s t r a$ 是 $O(N^2)$ 的，堆优化版的 $D ijk s t r a$ 是 $O(m\cdot logN)$ 的，这里有个最简单的判断方式，就是稠密图就用朴素版的，稀疏图就用堆优化版的，所以这里选择堆优化版的，然后建图方式就正常的邻接表，建图也很明显，然后其余就是模板了，详情见代码。

题目描述：

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。每条道路有一个通过费用（包括油费，过路费等等）。给定一个地图，包含 C 条直接连接 2 个城镇的道路。每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。数据保证至少存在一条道路。数据范围
1≤T≤2500,1≤C≤62001≤Ts,Te,Rs,Re≤T,1≤Ci≤1000
输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 3000, M = 15010, INF = 0x3f3f3f3f;int n, m, S, E;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[S] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0,S});while(heap.size()){auto t = heap.top(); heap.pop();int v = t.x, p = t.y;if(st[p]) continue;st[p] = true;for(int i = h[p]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[p] + w[i]){dist[j] = dist[p] + w[i];heap.push({dist[j], j});	}	}}return dist[E]; 
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n >> m >> S >> E;while(m--){int a, b, c; cin >> a >> b >> c;add(a,b,c), add(b,a,c);}cout << dijkstra() << endl;return 0;
}

二、信使

标签：单源最短路

思路：一眼一看就是求起点到每个点的最大距离是多少，如果是 $I NF$ 说明至少存在一个点不能到达，然后建图就是正常的方式，因为是稠密图所以采用邻接矩阵来存，最短路算法采用朴素版的 $D ijk s t r a$ ，但这个数据范围比较小所以拿啥存都可以，但是比赛的时候就不会是这样了，数据范围会卡的很死，有时也会卡常数。其余就是模板了。

题目描述：

战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。直至所有 n 个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。输入格式
第 1 行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要
花费 k 天。输出格式
一个整数，表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信，就输出-1。数据范围
1≤n≤100,1≤m≤200,1≤k≤1000
输入样例：
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例：
11

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = 410, INF = 0x3f3f3f3f;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < n - 1; ++i){int t = -1;for(int j = 1; j <= n; ++j){if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;}st[t] = true;for(int j = 1; j <= n; ++j) dist[j] = min(dist[j], dist[t] + g[t][j]);}int maxv = 0;for(int i = 1; i <= n; ++i) maxv = max(maxv, dist[i]);return maxv;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(g, 0x3f, sizeof g);cin >> n >> m;while(m--){int a, b, c; cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c);}int t = dijkstra();if(t == INF) cout << -1 << endl;else cout << t << endl;return 0;
}

三、香甜的黄油

标签：最短路、SPFA

思路：这道题是求所有的奶牛到达某一个点的距离和最小，首先所有奶牛到达一个点的距离和，我们可以将该点当作起点，然后到达奶牛的点的最短距离加起来即可。然后我们可以枚举所有的点，总的时间复杂度为 $O(n\cdot m)$ ，通过数据范围我们得知时间复杂度是在 $10^5$ ，所以是可以的。因为已经默认最短路算法用 $s p f a$ 了，堆优化版的 $D ijk s t r a$ 也是可以的，时间复杂度为 $O(n\cdot mlongN)$ ，这里自己任意选择，因为还没写过 $s p f a$ ，所以这里就写一下，然后现在的比赛一般都会卡 $s p f a$ 的，但是 $O I$ 赛制是有过程分的，影响不是特别大，但建议在数据范围允许的情况下，用堆优化版的 $D ijk s t r a$ ，因为有时候就是这几分决定一个奖项。

题目描述：

农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。数据保证至少存在一个牧场和所有牛所在的牧场连通。输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。输出格式
共一行，输出奶牛必须行走的最小的距离和。数据范围
1≤N≤500,2≤P≤800,1≤C≤1450,1≤D≤255
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 810, M = 3000, INF = 0x3f3f3f3f;int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
int id[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int spfa(int S)
{memset(dist, 0x3f, sizeof dist);dist[S] = 0, st[S] = true;queue<int> q; q.push(S);while(q.size()){int t = q.front(); q.pop();st[t] = false;for(int i = h[t]; i != -1; i = ne[i]){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);}}}int sum = 0;for(int i = 1; i <= k; ++i) {int t = dist[id[i]];if(t == INF) return INF;sum += t;}return sum;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> k >> n >> m;for(int i = 1; i <= k; ++i) cin >> id[i];while(m--){int a, b, c; cin >> a >> b >> c;add(a,b,c), add(b,a,c);}int minv = 2e9;for(int i = 1; i <= n; ++i) minv = min(minv, spfa(i));cout << minv << endl;return 0;
}

四、最优乘车

标签：单源最短路

思路：这道题问的是最少的换站次数，我们可以在一个公交线路中，把每一个站与它后面的所有站都建一条边权值为一，所以最优的换车次数就是从起点到终点的最短距离减一。由于这道题的边权都是正的且全部相等，所以我们可以用 $BFS$ 来做，时间复杂度为 $O (n + m)$ ，但由于该题是一个稠密图，所以用邻接矩阵来存，实际的时间复杂度为 $O(N^2)$ ，然后就是模板了，其实这个图的 $BFS$ 自己一直拿的是邻接表写的，所以第一次写邻接矩阵还不太适应，不过只要思路清楚还是很好写的。

题目描述：

H 城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到 H 城旅游，他很想去 S 公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘
某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。现在用整数 1,2,…N 给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N
。写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按
运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出 NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。数据范围
1≤M≤100,2≤N≤500
输入样例：
3 7
6 7
4 7 3 6
2 1 3 5
输出样例：
2

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 510, M = 110, INF = 0x3f3f3f3f;int n, m;
bool g[N][N];
int dist[N];
string line;
int path[N];int bfs()
{memset(dist, -1, sizeof dist);dist[1] = 0;queue<int> q; q.push(1);while(q.size()){int t = q.front(); q.pop();for(int i = 1; i <= n; ++i){if(dist[i] == -1 && g[t][i]){dist[i] = dist[t] + 1;q.push(i);}}}return dist[n];
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> m >> n;getline(cin, line);while(m--){getline(cin, line);stringstream ssin(line);int t = 0, cnt = 0;while(ssin >> t) path[cnt++] = t;for(int i = 0; i < cnt; ++i){for(int j = i + 1; j < cnt; ++j){g[path[i]][path[j]] = true;}}}int t = bfs();if(t == -1) cout << "NO" << endl;else cout << max(0, t - 1) << endl;return 0;
}

五、最小花费

标签：最短路、Dijkstra

思路：这道题也是一个最短路问题，我们可以看成从 $\rarr A$ 会有权重的增加，然后看找到达终点的权重最小的那一条路径，其实就是最短路问题了，只不过原来的权重计算是 $d i s t [j] = d i s t [p] + w [i]$ ，而现在成了 $\frac{100}{w[i]}$ ，因为 $\frac{100-Z}{100} = B$ ，所以 $\frac{100}{100-z}$ ，我们在处理的时候把 $w [i]$ 处理成 $100 - Z$ 即可，初始的 $d i s t [B] = 100.0$ ，然后就是套模板即可，详情见代码。

题目描述：

在 n 个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100)。最后一行输入两个正整数 A,B。数据保证 A 与 B 之间可以直接或间接地转账。输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。精确到小数点后 8 位。数据范围
1≤n≤2000,m≤105
输入样例：
3 3
1 2 1
2 3 2
1 3 3
1 3
输出样例：
103.07153164

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<double,int> PSI;
#define x first
#define y secondconst int N = 2010, M = 2e5+10, INF = 0x3f3f3f3f;int n, m, S, E;
int h[N], e[M], w[M], ne[M], idx;
double dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}double dijkstra()
{for(int i = 1; i <= n; ++i) dist[i] = DBL_MAX;dist[E] = 100.0;priority_queue<PSI, vector<PSI>, greater<PSI>> heap;heap.push({100.0,E});while(heap.size()){auto t = heap.top(); heap.pop();int p = t.y;if(st[p]) continue;st[p] = true;for(int i = h[p]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[p] * (100.0 / w[i])){dist[j] = dist[p] * (100.0 / w[i]);heap.push({dist[j],j});}}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(h, -1, sizeof h);cin >> n >> m;while(m--){int a, b, c; cin >> a >> b >> c;c = 100 - c;add(a,b,c), add(b,a,c);}cin >> S >> E;dijkstra();printf("%.8f\n", dist[S]);return 0;
}

六、昂贵的聘礼

标签：最短路、Dijkstra

思路：这道题其实就是建图比较难，我们可以建立一个虚拟源点 $0$ ，然后从该点到任意一件物品代表买这件物品，边权代表买这件物品的价格，所以我们可以建出一个图，然后答案就被变成从 $0\rarr 1$ 所花费的最小价值，然后再遍历的时候把等级的范围加进去即可，详情见代码。

题目描述：

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用 10000 个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 5000 金
币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。为了方便起见，我们把所有的物品从 1 开始进行编号，酋长的允诺也看作一个物品，并且编号总是 1。每个物品都有对应的价格 P，主人的地位等级 L，以及一系列的替代品 Ti 和该替代品所对应的”优惠” Vi。如果两人地位等级差距超过了 M，就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。输入格式
输入第一行是两个整数 M，N，依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了 N 个物品的描述。每个物品的描述开头是三个非负整数 P、L、X，依次表示该物品的价格、主人的地位等级和替代品总数。接下来 X 行每行包括两个整数 T 和 V，分别表示替代品的编号和”优惠价格”。输出格式
输出最少需要的金币数。数据范围
1≤N≤100,1≤P≤10000,1≤L,M≤N,0≤X<N
输入样例：
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
输出样例：
5250

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 110, M = N * N, INF = 0x3f3f3f3f;int n, m;
int g[N][N], level[N];
int dist[N];
bool st[N];int dijkstra(int down, int up)
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[0] = 0;for(int i = 0; i < n; ++i){int t = -1;for(int j = 0; j <= n; ++j){if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;}st[t] = true;for(int j = 0; j <= n; ++j) {if(level[j] >= down && level[j] <= up)dist[j] = min(dist[j], dist[t] + g[t][j]);}}return dist[1];
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);memset(g, 0x3f, sizeof g);cin >> m >> n;for(int i = 1; i <= n; ++i){int p, l, cnt; cin >> p >> level[i] >> cnt;g[0][i] = min(g[0][i], p);while(cnt--){int t, v; cin >> t >> v;g[t][i] = min(g[t][i], v);}}int minv = 2e9;for(int i = level[1] - m; i <= level[1]; ++i) minv = min(minv, dijkstra(i,i+m));cout << minv << endl;return 0;
}