单元最短路的建图方式
@TOC
1.首先我们先来复习求单元最短路有哪些算法
边权均非负的情况下：
朴素dijkstra O(n^2)void dijkstra() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); dist[1] = 0; //循环n次 for (int k = 0; k < n; k++) { int t = 0; for (int j = 1; j <= n; j++) { if (!st[j] && dist[j] < dist[t]) t = j; } st[t] = true; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; dist[j] = min(dist[j], dist[t] + w[i]); } } }堆优化版的dijkstra O(mlog(n))void heap_dijkstra(int x) { priority_queue<PII, vector<PII>, greater<PII>> heap; memset(dist, 0x3f, sizeof dist); dist[x] = 0; heap.push({0, x}); while (heap.size()) { auto t = heap.top(); heap.pop(); int u = t.y; if (st[u]) continue; st[u] = true; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[u] + w[i]) { dist[j] = dist[u] + w[i]; heap.push({dist[j], j}); } } } }spfa 最快:O(m) 最慢: O(mn)void spfa() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); st[1] = true; dist[1] = 0; 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]) q.push(j); } } } }
2.题目
题目1 ：AcWing 1129. 热浪
这道题就是一套纯裸求单源最短路的题目，用上面三种算法都可以过
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3, M = N * N;
int T, C, Ts, Te;
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++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[Ts] = 0;
for (int k = 1; k <= T; k++)
{
int t = 0;
for (int j = 1; j <= T; j++)
{
if (!st[j] && dist[j] < dist[t])
{
t = j;
}
}
if (t == Te)
{
return;
}
st[t] = true;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
dist[j] = min(dist[j], dist[t] + w[i]);
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> T >> C >> Ts >> Te;
for (int i = 0; i < C; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dijkstra();
cout << dist[Te];
return 0;
}题目2 AcWing 1128. 信使
这道题也是一道比较裸的单元最短路题目，求每一个点到其他点的最短时间，最后要求整个送信过程最短时间，所以就是最后一个得到新的哨点的时间，即max[dist[]]
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3, M = N * N;
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++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int k = 1; k <= n; k++)
{
int t = 0;
for (int j = 1; j <= n; j++)
{
if (!st[j] && dist[j] < dist[t])
{
t = j;
}
}
st[t] = true;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
dist[j] = min(dist[j], dist[t] + w[i]);
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dijkstra();
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans = max(ans, dist[i]);
if (dist[i] == 0x3f3f3f3f)
{
cout << -1;
return 0;
}
}
cout << ans;
return 0;
}题目3：AcWing 1127. 香甜的黄油
这道题不是单源最短路了，是求多源最短路，我们需要选定一个起点，求最优解，由于我们不知道哪个点是最优解，所以我们要把所有的牧场枚举一遍，求以某个牧场作为起点的路径和，最后取所有路劲和的最小值。
- Floyd : 复杂度
O(n^3)会超时，不可行 - 朴素版dijkstra ，本题中，因为需要枚举每个点，所以复杂度是
n * O(n^2) = O(n^3)，n=800，所以会超时 - 堆优化版的dijkstra, 复杂度
O(mnlog(n))，勉强可以过 - spfa 复杂度最低：
O(mn),如果出题人不卡的话是可以过的
所以这道题我就用spfa来写了，可以过，而且很快
#include <bits/stdc++.h>
using namespace std;
const int N = 810, M = 3000;
int h[N], w[M], ne[M], e[M], idx;
int s[N];
int dist[N];
bool st[N];
int n, p, m;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int x)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
st[x] = true;
dist[x] = 0;
queue<int> q;
q.push(x);
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])
q.push(j);
}
}
}
}
signed main()
{
memset(h, -1, sizeof h);
cin >> n >> p >> m;
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
s[t]++;
}
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
int ans = 1e9;
for (int i = 1; i <= p; i++)
{
int sum = 0;
int f = 1;
spfa(i);
for (int j = 1; j <= p; j++)
{
if (s[j] && dist[j] == 0x3f3f3f3f)
{
f = 0;
break;
}
sum += dist[j] * s[j];
}
if (f)
{
ans = min(ans, sum);
}
}
cout << ans;
return 0;
}题目4：AcWing 1126. 最小花费
写图论的难点其实不在于求最短路的过程，而在于建图，把图建好了，问题也就很容易解决了。
d[] 是金钱，w[]是转账的汇率， 0<w<=1
这道题中A最少需要多少钱使得转账后B收到100元，我们可以列出这样一个式子：d[A] * w1 * w2 *... wn = d[B] = 100，A最少，那么w1 * w2 * .. wn 就要最大 ，即 求log(w1∗w2∗w3..)=log(w1)+log(w2)+..log(w1∗w2∗w3..)=log(w1)+log(w2)+.. 最大，
因为w都是小于1的，所以log(w)都是小于0的，所以将每个数取相反数，
问题转化成求取反后的最小值，即转换成最短路问题，这道题我们可以发现不光加一个数可以求最短路，乘一个数也可以求最短路
我们已经将这道题解析求最短路问题，但不是真的求最短路，我们还是要求w1 * w2 * .. wn的最大值，也就是求最长路
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010;
int n, m, S, T;
double g[N][N];
double dist[N];
bool st[N];
void dijkstra()
{
dist[S] = 1;
for (int i = 1; i <= n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] < dist[j]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = max(dist[j], dist[t] * g[t][j]);
}
}
int main()
{
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
double z = (100.0 - c) / 100;
g[a][b] = g[b][a] = max(g[a][b], z);
}
cin >> S >> T;
dijkstra();
printf("%.8lf\n", 100 / dist[T]);
return 0;
}这里还有另外一种写法，d[A] * w1 * w2 *... wn = d[B] = 100，那么可以转换为d[A] = d[B] / (w1 * w2 * ... wn),由于w<=1，所以分子小于等于1，d[B]/w>=d[A]所以为了d[A]最小，那么d[B] / w最小，那么就转换成了求由B到A的最短路问题
代码2
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 2e5 + 10;
int h[N], w[M], ne[M], e[M], idx;
bool st[N];
double dist[N];
int n, m;
int A, B;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa()
{
for (int i = 0; i <= n; i++)
dist[i] = 1e9;
memset(st, 0, sizeof st);
st[B] = true;
dist[B] = 100;
queue<int> q;
q.push(B);
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] * 100 / (100 - w[i]))
{
dist[j] = dist[t] * 100 / (100 - w[i]);
if (!st[j])
q.push(j);
}
}
}
}
signed main()
{
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 >> A >> B;
spfa();
printf("%.8lf", dist[A]);
return 0;
}总结
- 当算乘积最值的最短路时，如果乘数都>=0,那么就边权都为非负数，那么可以用
dijkstra... - 如果乘数有
<0的，那么只能用spfa...
题目5：AcWing 920. 最优乘车
这道题就非常考验建图能力了
分析：题目时要求最少换乘次数，换乘不好求，我们可以先求坐车次数，坐车次数-1=换乘次数,因为第一上车不算换乘，那么在一条线路a b c d中，我们可以假设从a上车，那么走到 b c d任意一个站都需要上车一次就可以到达，从b上车，那么走到c d任意一个站也只需要上车一次就可以到达，假设现在还有另一条线路c e f ，我们要到f 站，就可以从c点下车，在上到这辆车上做到f，那么c 到f也只需要上车一次就可以了。
这样我们就可以知道如何建图了，只要在一条线路上可以到达，那么这两个站就可以连一条边权为1的边，最后就变成了从1到n的最短路问题
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> Q;
#define x first
#define y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int N = 1000, M = 1e3;
int m, n;
int h[N], w[M], ne[M], e[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
Q q;
q.push({0, 1});
while (q.size())
{
auto t = q.top();
q.pop();
int u = t.y;
if(st[u])
continue;
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[u] + w[i])
{
dist[j] = dist[u] + w[i];
q.push({dist[j], j});
}
}
}
return ;
}
int main()
{
cin >> m >> n;
getchar();
memset(h, -1, sizeof h);
while (m--)
{
string s;
getline(cin, s);
vector<int> v;
int k = 0;
for (int i = 0; i < s.size(); i++)
{
if (isdigit(s[i]))
k = k * 10 + s[i] - '0';
else
{
v.push_back(k);
k = 0;
}
}
v.push_back(k);
for (int i = 0; i < v.size() - 1; i++)
{
for (int j = i + 1; j < v.size(); j++)
{
add(v[i], v[j], 1);
}
}
}
dijkstra();
if(dist[n] == 0x3f3f3f3f)
cout <<"NO";
else
cout << dist[n] - 1;
return 0;
}题目4：AcWing 903. 昂贵的聘礼
这道题还是考验建图分析模型能力
分析：取酋长的女儿需要10000个金币，但是探险家拿不出这么多金币，但是可以通过其他物品交换来代替这10000个金币，酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要 8000 金币。如果你能够弄来他的水晶球，那么只要 5000 金币就行了。” 那么娶酋长女儿 = 10000 = 皮袄 + 8000 = 水晶球 + 5000，10000个金币我没有，那这俩替代品是不是可以弄来呢，所以又用其他东西来换，到最后探险家如何用最少的金币娶他的女儿呢？
（这让我想起了之前看到的一些视频关于如何用一块钱去和别人换东西，用换来的物品在和其他人交换，最后通过1块钱换到了很贵重的东西，哈哈哈，有机会我也想试一试）
我们先来建立一下模型：
建立模型之后，我们发现这题就是求单源最短路的问题，最终是求到酋长女儿的最少金币，题目已经给出n个物品的信息，那用什么来表示探险家呢，这里我们可以建立一个==虚拟源点==，用0号点表示，用0号点来向其他点建图，最后求一边最短路即可。
还要这道题有个要求，就是交换的东西之间都有一个等级，不能超过一个范围，探险家最终要和酋长女儿交换，所以她俩的等级差不能超过范围，其他所有交换的中介都不能超过这个范围，直接枚举探险家的等级即可，最后算最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef priority_queue<int, vector<int>, less<int>> Q;
#define x first
#define y second
const int N = 110, M = N * N;
int h[N], w[M], ne[M], e[M], idx;
bool st[N];
int dist[N];
int level[N];
int n, m;
int ans = 1e9;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int l, int r)
{
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
st[0] = true;
dist[0] = 0;
queue<int> q;
q.push(0);
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 (level[j] >= l && level[j] <= r && dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
q.push(j);
}
}
}
}
signed main()
{
memset(h, -1, sizeof h);
cin >> m >> n;
for (int i = 1; i <= n; i++)
{
int c, l, cnt;
cin >> c >> level[i] >> cnt;
add(0, i, c);
while (cnt--)
{
int t, v;
cin >> t >> v;
add(t, i, v);
}
}
// 等级范围
for (int i = level[1] - m; i <= level[1]; i++)
{
spfa(i, i + m);
ans = min(ans, dist[1]);
}
cout << ans;
return 0;
}总结
通过本节我们学到了关于如果求单元最短路的一些问题，重点在如何建图上，将问题转化为图论模型。
- 虚拟源点
- 建图
- 边权（加 / 乘）
- 多源最短路转化为单元最短路
有任何疑问欢迎评论区留言哦
