算法刷题day26：单源最短路

本文主要是介绍算法刷题day26：单源最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

引言

今天刷题刷的是单源最短路问题，也就是图论中的搜索的问题，这个问题还是非常常考的，其实模板只要背熟了，理解到位了，剩下的主要是建图和一些细节的问题，除了背模板理解原理，再就是多刷题、多见题了，加油！

一、热浪

标签：单源最短路

思路： $s p f a$ 算法，可参考博客最短路问题，这种单源最短路问题，只要图建好了，起点和终点规定了，就没啥难的了，就是模板。

题目描述：

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。农夫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≤6200,1≤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;const int N = 3000, M = 7000 * 2, 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 spfa()
{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);}}}}if(dist[E] == INF) return -1;else 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 << spfa() << endl;return 0;
}

二、信使

标签：单源最短路

思路：就是求从第一个哨所，到全部的哨所所需花费的最短时间， $s p f 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;const int N = 200, M = 300, INF = 0x3f3f3f3f;int n, m;
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 spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;st[1] = true;queue<int> q;q.push(1);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 res = 0;for(int i = 1; i <= n; ++i) {if(dist[i] == INF) return -1;res = max(res, dist[i]);}return res;
}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;add(a,b,c);add(b,a,c);}cout << spfa() << endl;return 0;
}

三、香甜的黄油

标签：单源最短路

思路：本来以为是超级源点问题，结果发现即使有了超级源点也不行，因为没有确定那个牧场是在哪。一看题解，原来是直接找从每个点到奶牛所在的牧场路程和的最小值，暴力枚举每个点就行了。数据范围也允许。

题目描述：

农夫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;const int N = 1000, M = 5000, 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];  // 第i号牧场有几头牛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 res = 0;for(int i = 0; i < k; ++i){int j = id[i];if(dist[j] == INF) return INF;else res += dist[j];}return res;
}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 = 0; 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 res = INT_MAX;for(int i = 1; i <= n; ++i) res = min(res, spfa(i));cout << res << endl;return 0;
}

四、最小花费

标签：单源最短路

思路：这道题其实可以看成找汇率最大的那一条路就行了，只要把 $s p f a$ 算法中的判断条件改一下，把原来的 $d i s t [j] > ...$ 改为 $d i s t [j] < ...$ ，因为如果从原点出发最后到终点，肯定是找变化率最大的那条路，这样一改小的就会被大的更新，最后在转换一下就行，详情见代码。

题目描述：

在  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> PII;const int N = 2010, M = 1e5+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()
{dist[S] = 1;priority_queue<PII> heap;heap.push({1,S});while(heap.size()){auto t = heap.top(); heap.pop();double v = t.first;int p = t.second;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] * (1.0 - w[i]/100.0)){dist[j] = dist[p] * (1.0 - w[i]/100.0);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;while(m--){int a, b, c;cin >> a >> b >> c;add(a,b,c), add(b,a,c);}cin >> S >> E;printf("%.8lf\n", 100.0 / dijkstra());return 0;
}