单源最短路（一）
2022/4/15 6:12:44
本文主要是介绍单源最短路（一），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
单源最短路建图，应用，扩展。
重新给图论提高课做一个总结。
建图方式
对于一个含有\(n\)个点，\(m\)条边的无向图，边权都是正值，求解起点到终点的最短距离。
根据\(n,m\)的数据范围选择邻接表或者邻接矩阵直接建图跑最短路就行，属于裸的板子题，难点在于如何抽象出图论模型来改板子吧。
多做多见多积累吧，灵光一现或许就是平时的日积月累的结果。
例题
题目：热浪
地址：https://www.acwing.com/problem/content/1131/
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2510, M = 2*6500+10;
int h[N],e[M],ne[M],w[M],dis[N],q[N];
int n,m,S,T,idx;
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 spfa() {
memset(dis, 0x3f, sizeof dis);
dis[S] = 0;
st[S] = true;
int hh = 0, tt = 1;
q[0] = S;
while( hh != tt ) {
int t = q[hh++];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
dis[j] = dis[t] + w[i];
if( !st[j] ) {
q[tt++] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main(void) {
cin >> n >> m >> S >> T;
memset(h, -1, sizeof h);
for (int i = 0; i < m; ++i ) {
int a,b,c;
cin >> a >> b >> c;
add(a,b,c), add(b,a,c);
}
spfa();
cout << dis[T] << endl;
return 0;
}
题目：信使
地址：https://www.acwing.com/problem/content/1130/
求从起点出发，到所有点的最短距离的集合中的最大值，最远的都到了，其他点肯定早或同时收到信号。
本题求的是最长路，把代码的比较符号改改就行，数据量比较小。
Code
#include <bits/stdc++.h>
using namespace std;
int g[200][200];
int n, m;
int main() {
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
int res = -1;
for (int i = 1; i <= n; i++) {
if (g[1][i] == 0x3f3f3f3f) {
res = -1;
break;
} else {
res = max(res, g[1][i]);
}
}
printf("%d\n",res);
return 0;
}
题目：香甜的黄油
地址：https://www.acwing.com/problem/content/1129/
有\(n\)个点，\(m\)条边，边权都是正值。
求给定起点下，到达所有牧场的最短距离。
spfa可以解决，但是关于spfa它已经死了，所以保险起见我们最好跑堆优化的dijksra算法。
本题枚举所有点为起点，找一下该点到达所有点的最小值即可，数据范围较小。
Code
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 123456789;
int n, p, c;
int dist[803], id[803];
bool vis[803];
vector<PII> e[1000];
int spfa(int start) {
memset(dist,0x3f,sizeof dist);
memset(vis,false,sizeof vis);
queue<int> q;
q.push(start);
dist[start] = 0;
vis[start] = 0;
while (q.size()) {
int now = q.front();
q.pop();
vis[now] = false;
for (auto ver : e[now]) {
if (dist[ver.fi] > dist[now] + ver.se) {
dist[ver.fi] = dist[now] + ver.se;
if (!vis[ver.fi]) {
vis[ver.fi] = true;
q.push(ver.fi);
}
}
}
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (dist[id[i]] == 0x3f3f3f3f) return 0x3f3f3f3f;
else sum += dist[id[i]];
}
return sum;
}
int main(void) {
scanf("%d%d%d",&n,&p,&c);
for (int i = 1; i <= n; i++) {
scanf("%d",&id[i]);
}
for (int i = 1; i <= c; i++) {
int u, v, w;
scanf("%d%d%d",&u,&v,&w);
e[u].pb({v,w});
e[v].pb({u,w});
}
int ans = inf;
for (int i = 1; i <= p; i++) {
ans = min(ans, spfa(i));
}
printf("%d\n",ans);
return 0;
}
题目：最小花费
地址：https://www.acwing.com/problem/content/1128/
\(X * w_i*w_i+1...=100\)，求X的最小值，即求后面一连串的最大值。
类比成求最长路，跑一个图论板子即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(X) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 123456789;
int n, m, s, e;
double dist[503];
bool vis[503];
double g[503][503];
void dijskra() {
dist[s] = 1;
for (int i = 1; i <= n; i++) {
int ver = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (ver == -1 || dist[ver] > dist[j])) {
ver = j;
}
}
vis[ver] = true;
for (int j = 1; j <= n; j++) {
dist[j] = max(dist[j], dist[ver] * g[ver][j]);
}
}
}
int main(void) {
scanf("%d%d",&n,&m);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
double w = (100.0-c)/100;
g[a][b] = g[b][a] = max(g[a][b],w);
}
scanf("%d%d",&s,&e);
dijskra();
printf("%.8lf\n",100/dist[e]);
return 0;
}
题目：最优乘车
地址：https://www.acwing.com/problem/content/922/
题意：
某个旅客想去公园游玩，但是他目前所在的地点没有一辆直达的巴士，他可能需要换乘几次后才能到达公园，现在给出所有巴士站编号和所有巴士路线，询问旅客到达公园的最少换乘次数。
思路：
换乘几次 = 乘车几次-1
可以看出，一条巴士路线上的所有巴士站，都可以沿着路线一直往后走，只算一次乘车，即答案+1。
那么我们可以建立一个权值都是1的图来进行求解，在这里如果我们直接依据题意建图，即一条线路上两两站点连线来求这个答案，显然是非常麻烦的，比如一个站点有多条线路时，你到下一站是属于换乘还是一条线路的判断，非常麻烦。
所以我们可以换一种灵活的建图方法，我们将一条线路上前面车站到后边可达车站建上一条边权为1的边即可，然后直接跑BFS即可。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int stop[1500], dist[503];
bool g[503][503];
void bfs() {
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
while (q.size()) {
int v = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (g[v][i] && dist[i] > dist[v] + 1) {
dist[i] = dist[v] + 1;
q.push(i);
}
}
}
}
int main() {
cin >> m >> n;
string line;
getline(cin,line);
while (m--) {
getline(cin,line);
stringstream ssin(line);
int cnt = 0, p;
while (ssin >> p) { stop[cnt++] = p; }
for (int j = 0; j < cnt; j++) {
for (int k = j + 1; k < cnt; k++) {
g[stop[j]][stop[k]] = true;
}
}
}
bfs();
if (dist[n] == 0x3f3f3f3f) {
cout << "NO" << endl;
} else {
cout << dist[n]-1 << endl;
}
return 0;
}
综合应用
例题
题目：选择最佳线路
地址：https://www.acwing.com/problem/content/1139/
题意：
n个点m条边的有向图，不知道起点S，但知道终点E，求解从每个起点出发到达任意终点的所有路线的最短距离。
分析：
-
算法1
人为确定一个虚拟源点，并且虚拟源点练到所有起点一条边权为0的边，即原问题转化为从虚拟源点出发到达终点E的最短路。
-
算法2
反向建图，把终点置为起点，求终点开始到所有起点的单源最短路，再在之中取个最小值。
Code
感觉用SPFA的话，可以把所有起点压入队里跑。
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(X) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const int N = 10010, M = 200010;
int n, m, s, idx;
int h[N], ne[M], e[M], w[M];
int dist[N];
bool vis[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void spfa() {
memset(dist,0x3f,sizeof dist);
queue<int> q;
q.push(0);
vis[0] = true;
dist[0] = 0;
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = false;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[u] + w[i]) {
dist[j] = dist[u] + w[i];
if (!vis[j]) {
vis[j] = true;
q.push(j);
}
}
}
}
}
int main(void) {
IO
while (cin >> n >> m >> s) {
memset(h,-1,sizeof h);
idx = 0;
rep(i,1,m) {
int a, b, c;
cin >> a >> b >> c;
add(a,b,c);
}
int T;
cin >> T;
while (T--) {
int ver;
cin >> ver;
add(0,ver,0);
}
spfa();
if (dist[s] == inf) {
cout << "-1\n";
} else {
cout << dist[s] << '\n';
}
}
return 0;
}
题目：拯救大兵瑞恩
地址：https://www.acwing.com/problem/content/1133/
题意：
巴拉巴拉巴拉太长了自己看。
分析：
简易版本：一个迷宫，从起点S走到终点E的最短路长度，每个格子可上下左右四个方向扩展，格子的属性有两种，连通和不连通（有障碍物），需要记录的状态就是当前坐标以及到达当前坐标的长度，可扩展坐标和可扩展坐标最短路长度。
到本题这里，格子的属性更复杂了，可以直达的格子里分为有钥匙和没钥匙两种，拿去钥匙不计时间，有障碍物的格子分为不可达的障碍物，或者需要某一类钥匙才可以通过的门。
那么我们需要记录的状态也就更多了，除了上述状态，还需要记录此时持有钥匙的状态，即我们需要维护一个三维状态\(f(x,y,state)\)，来表明在\((x,y)\)这个坐标时的持有钥匙状态。
接下来我们考虑走到下一个格子后，如何进行状态处理。本题因为可以走回头路，不存在拓扑序，存在环形路径的可能，所以用DP无法计算状态转移，需要使用最短路算法。
我们定义当前点为\((x,y)\)，状态为\(state\)。
- 如果存在钥匙，我们一定会拿起来，因为拿钥匙不消耗时间（等于边权为0），多多益善。那么会得到状态\(f'(x,y,state')\)，比较当前状态的最短路长度，如果\(d[f']<=d[f]\)，则不进行任何处理，新状态更优，且已在队伍里。反之将更新为目前状态的最短路径长度，将其压入队头。
- 没有钥匙，就照常往四个方向进行扩展延伸，将新的可以到达状态压入队列尾部，等待下一次扩展。
本题空间为64MB，直接开三维数组存状态会MLE，所以我们将状态压缩一下，将\((x,y)\)压缩成一个独立的点来表示，每类钥匙可以用二进制来表示，拿起钥匙就是|一下，将对应位置1即可，判断有无钥匙则将状态右移对应位看是不是1就可以。
建图细节看代码，这里不再赘述。
Code
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(X) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 123456789;
const int N = 11, M = 400, P = 1 << 10;
int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];
int dist[N*N][P];
bool vis[N * N][P];
set<PII> Edge;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void build() {
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int u = 0; u < 4; u++) {
int x = i + dx[u], y = j + dy[u];
if (!x || x > n || !y || y > m) continue;
int a = g[i][j], b = g[x][y];
if (!Edge.count({a,b})) {
add(a,b,0);
}
}
}
}
}
int bfs() {
memset(dist,0x3f,sizeof dist);
dist[1][0] = 0;
deque<PII> q;
q.push_back({1,0});
while (q.size()) {
PII u = q.front();
q.pop_front();
if (vis[u.fi][u.se]) continue;
vis[u.fi][u.se] = true;
if (u.fi == n * m) {
return dist[u.fi][u.se];
}
if (key[u.fi]) {
int state = u.se | key[u.fi];
if (dist[u.fi][state] > dist[u.fi][u.se]) {
dist[u.fi][state] = dist[u.fi][u.se];
q.push_front({u.fi, state});
}
}
for (int i = h[u.fi]; i != -1; i = ne[i]) {
int j = e[i];
if (w[i] && !(u.se >> w[i]-1 & 1)) continue;
if (dist[j][u.se] > dist[u.fi][u.se] + 1) {
dist[j][u.se] = dist[u.fi][u.se] + 1;
q.push_back({j,u.se});
}
}
}
return -1;
}
int main(void) {
IO
cin >> n >> m >> p >> k;
for (int i = 1, t = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
g[i][j] = t++;
}
}
memset(h,-1,sizeof h);
while (k--) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int a = g[x1][y1], b = g[x2][y2];
Edge.insert({a,b}), Edge.insert({b,a});
if (c) {
add(a,b,c), add(b,a,c);
}
}
build();
int s;
cin >> s;
while (s--) {
int x, y, c;
cin >> x >> y >> c;
key[g[x][y]] |= 1 << c-1;
}
cout << bfs() << '\n';
return 0;
}
题目：最短路计数
地址：https://www.acwing.com/problem/content/1136/
题意：
给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1到 N。
问从顶点 1 开始，到其他每个点的最短路有几条。
分析:
先前条件：最短路中不存在值为0的环，否则可以一直在环里跑，无解。
先前概念：最短路径树指的是以某个节点为根，根节点到其他点距离最小形成的一棵树。
从每个点的前一个路径考虑，看看该点时从哪个路径转移过来的，累加上来就好，但是我们需要先弄出来一个最短路径树(拓扑图)。对于转移过来的边，我们根据长度为两种。
- 长度比当前大许多，即沿着这条路线伸展出来的路才是我们需要的最短路。
- 长度差1，说明是我们当前节点延伸出去且是当前长度为当前最短路，直接累加上去。
对于最短路径树，我们可以通过BFS算法或者dijkstra算法实现。
- BFS每次扩展一层，最后一定能够得到拓扑图。
- dijkstra每次出队距离起点最近的点，如果知道用的是哪条边，连起来就是一颗最短路树。
Code
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(X) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 123456789;
const int N = 100010, M = 400010;
const int mod = 100003;
int n, m;
int h[N], e[M], ne[M], q[M];
int dist[N], cnt[N];
int idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs() {
memset(dist,0x3f,sizeof dist);
dist[1] = 0, cnt[1] = 1;
int front = 0, rear = 0;
q[0] = 1;
while (front <= rear) {
int t = q[front++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + 1) {
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q[++rear] = j;
} else if (dist[j] == dist[t] + 1) {
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main(void) {
IO
cin >> n >> m;
memset(h,-1,sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a,b),add(b,a);
}
bfs();
for (int i = 1; i <= n; i++) {
cout << cnt[i] << "\n";
}
return 0;
}
题目：观光
地址：https://www.acwing.com/problem/content/385/
题意：
求次短路长度数目。
分析：
和上一题差不多，只不过状态转移麻烦很多。
- 当前最短路变次短路，最短路得到更优结果，双双入队。
- 找到一条新的最短路，次数更新。
- 找到一条更优次短路，更新当前次短路状态，入队。
- 找到一条新的次短路，次数更新。
Code
#include <bits/stdc++.h>
using namespace std;
#define debug freopen("in.in","r",stdin);freopen("out.out","w",stdout);
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define pb push_back
#define SZ(X) ((int)(x).size())
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
const int inf = 123456789;
const int N = 1010, M = 100010;
int n, m, S, E, idx;
int h[N],ne[M],e[M],w[M];
int dist[N][2], cnt[N][2];
bool vis[N][2];
struct Node {
int id, type, dist;
bool operator > (const Node& tmp) const {
return dist > tmp.dist;
}
};
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dij() {
memset(vis,false,sizeof vis);
memset(dist, 0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
dist[S][0] = 0, cnt[S][0] = 1;
priority_queue<Node, vector<Node>, greater<Node>> heap;
heap.push({S,0,0});
while (heap.size()) {
Node u = heap.top();
heap.pop();
int ver = u.id, type = u.type, distance = u.dist, count = cnt[ver][type];
if (vis[ver][type]) continue;
vis[ver][type] = true;
for (int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j][0] > distance + w[i]) {
dist[j][1] = dist[j][0];
cnt[j][1] = cnt[j][0];
heap.push({j,1,dist[j][1]});
dist[j][0] = distance + w[i];
cnt[j][0] = count;
heap.push({j,0,dist[j][0]});
} else if (dist[j][0] == distance + w[i]) {
cnt[j][0] += count;
} else if (dist[j][1] > distance + w[i]) {
dist[j][1] = distance + w[i];
cnt[j][1] = count;
heap.push({j,1,dist[j][1]});
} else if (dist[j][1] == distance + w[i]) {
cnt[j][1] += count;
}
}
}
int res = cnt[E][0];
if (dist[E][1] - 1 == dist[E][0]) {
res += cnt[E][1];
}
return res;
}
int main(void) {
IO
int T;
cin >> T;
while (T--) {
cin >> n >> m;
memset(h,-1,sizeof h);
idx = 0;
while (m--) {
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
}
cin >> S >> E;
cout << dij() << '\n';
}
return 0;
}
这篇关于单源最短路（一）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-10SpringBoot 内部方法调用，事务不起作用的原因及解决办法
- 2024-11-10独立开发者 5 个月，月收入赶超北京工资，我的一点心得
- 2024-11-09程序员 SEO 系列：如何找到更多搜索关键词？
- 2024-11-09为何选择Spring AI Alibaba开发智能客服平台？
- 2024-11-09Sentinel不同的流控效果资料详解
- 2024-11-09Sentinel配置限流资料：新手入门教程
- 2024-11-09Sentinel配置限流资料详解
- 2024-11-09Sentinel熔断规则配置资料详解
- 2024-11-08Sentinel熔断规则配置资料详解
- 2024-11-08Sentinel限流资料入门教程
