首页 > 编程语言 >回顾图存储与最短路算法

回顾图存储与最短路算法

时间：2024-08-23 22:55:38浏览次数：10  
标签：存储 dj int 短路 head next 算法 edge dp

图的存储与最短路问题

一、图的储存

1.邻接矩阵

  • 邻接矩阵使用二维 v e c t o r vector vector 存储数据
  • d [ i ] [ j ] d[i][j] d[i][j] 表示从点 i i i 到点 j j j 的权值 有向图存储一个即可,无向图还需要存储 d [ j ] [ i ] d[j][i] d[j][i]

邻接矩阵图例

优点：

1.表示方式直接，直观易于理解

2.在稀疏图上节省空间

缺点：

1.二维 vector 在访问时会比较耗时

总结：邻接矩阵所以只适合处理 ∣ N ∣ < = 2500 |N|<= 2500 ∣N∣<=2500 的问题

2.链式前向星储存图

  • 以一个结构体将需要存储的图的四个参数存储起来
struct Edge{
    int u, v, w, next;
}edge[N];

u u u(起点), v v v(终点), w w w(权值), n e x t next next(上一个点的序号)

  • 以 h e a d head head存储最后一个 u u u 的序号, 同时head初始化为-1。

链式前向星

——图片仅供参考

这里 t o to to 相当于 v v v , f r o m from from 相当于 u u u

  • 链式前向星添加点的方式为：
void add_edge(int u,int v,int w){
   edge[e].u=u;
   edge[e].v=v;
   edge[e].w=w;
   edge[e].next=head[u];
   head[u]=e++;
}
  • 链式向前星的遍历方式为 ：
for (int u = 1; u <= n; u++) {
   cout << "u= " << u << '\n';
   for (int i = head[u]; i != -1; i = nxt[i]) {
       cout << "v= " << pnt[i] << ", w= " << wv[i] << '\n';
   }
}

优点：

1.省时间, 占用空间小

总结：链式前向星是目前最主流的储存图的方法, 推荐大家使用

——图的储存完

二、最短路算法

1. S P F A _ H E A P ( D i j k s t r a ( 迪杰斯特拉算法 ) + h e a p ( 堆优化 ) ) 1.SPFA\_HEAP(Dijkstra(迪杰斯特拉算法) + heap(堆优化)) 1.SPFA_HEAP(Dijkstra(迪杰斯特拉算法)+heap(堆优化))

——在这里我就直接向大家介绍堆优化过的迪杰斯特拉算法的最简写法，也是最好用的最短路算法

/*
SPFA 算法是 Bellman-Ford算法 的队列优化算法的称，
通常用于求含负权边的单源最短路径，以及判负权环
*/
//------------- 堆优化 dijkstra最短路 O(nlog(m))
vector<int> dj(m + 1, 200005), pd(n + 1, 0);
dj[s] = 0; 
//把起点的值设为0，表示起点自己到自己的最短路为0
priority_queue<pair<int, int>> q;
//用pair<int, int> 第一位是权值，第二位是u起点
q.push({dj[s], s});
while (!q.empty()) { 
//当q里面还有数时，表明还没有把起点到任意点的距离算完
	int k = 0;
	int w = q.top().first, u = q.top().second;
	w = -w;
	//因为我们插入时将w变成了-w,所以这里要反一下 
	q.pop();
	//更新完就弹出，表示已经更新过了
	if (dj[u] != w) continue;		
	// dp[p] != -w 表示 p 已经访问过
	for (int j = head[u]; j != -1; j = edge[j].next) {
		int v = edge[j].v, z = dj[u] + edge[j].w;
		if (dj[v] > z) q.push({-(dj[v] = z), v});
		// 因为优先队列每次弹出的都是最大的数
		//而我们希望每次从最小的数开始更新
		//所以插入时需要取反
	}
}
cout << dj[t];
/*------------- 堆优化 dijkstra最短路 O(nlog(m)) end ------*/

2. F l o y d ( 弗洛伊德算法 ) 2.Floyd(弗洛伊德算法) 2.Floyd(弗洛伊德算法)

迪杰斯特拉算法适合求固定两点的最短路，但如果要求一个图里面任意两点的最短路，推荐使用 F l o y d Floyd Floyd 算法

题目 :

  1. 给定一个 n 个点 m 条边的 有向图，图中可能存在重边和自环，边权可能为负数。

  2. 再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，输出 i m p o s s i b l e impossible impossible。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main() {
	int n, m, t;
	cin >> n >> m >> t;
	vector<vector<int>> dj(n + 1, vector<int> (n + 1, INF));
	// dj[u][v] 表示从 u 到 v 的 最短距离
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		dj[u][v] = min(dj[u][v], w);
		// 重边取较小
	}
	for (int i = 1; i <= n; i++) dj[i][i] = 0;
	// 自己到自己的距离为 0
	for (int k = 1; k <= n; k++) {
		for (int u = 1; u <= n; u++) {
			for (int v = 1; v <= n; v++) {
				if (u == k || u == v || k == v) continue;
				dj[u][v] = min(dj[u][v], dj[u][k] + dj[k][v]);
				// 经不经过第k个点
			}
		}
	}
	const int PD = 200000005;
	while (t--) {
		int u, v;
		cin >> u >> v;
		if (dj[u][v] < PD) cout << dj[u][v] << '\n';
		//是否为负环
		else cout << "impossible" << '\n';
	}
	return 0;
}

三、具体题目

1.非负权单源最短路

题目：给一个 n ( 1 ≤ n ≤ 1 0 5 ) n(1≤n≤10^5) n(1≤n≤105) 个点 m ( 1 ≤ m ≤ 2 ⋅ 1 0 5 ) m(1≤m≤2⋅10 ^ 5) m(1≤m≤2⋅105)条边的 无向图，所有边权都为正，求 s s s 到 t t t 的最短路。

这题直接套模板就好了

——代码如下 :

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {

	int n, m, s, t;
	cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++) {
		int u1, v1, w1;
		cin >> u1 >> v1 >> w1;
		add_edge(u1, v1, w1);
		add_edge(v1, u1, w1);
	}
	vector<int> dj(m + 1, 200005), pd(n + 1, 0);
	dj[s] = 0;
	priority_queue<pair<int, int>> q;
	q.push({dj[s], s});
	while (!q.empty()) {
		int k = 0;
		int w = q.top().first, u = q.top().second;
		// auto [w,u]=q.top();
		w = -w;
		q.pop();
		if (dj[u] != w) {
			continue;
		}

		for (int j = head[u]; j != -1; j = edge[j].next) {
			int v = edge[j].v, z = dj[u] + edge[j].w;
			if (dj[v] > z) q.push({-(dj[v] = z), v});
		}
	}
	cout << dj[t];
	return 0;
}

2.带负权单源最短路

题目：给一个 n ( 1 ≤ n ≤ 1 0 5 ) n(1≤n≤10^5) n(1≤n≤105) 个点 m ( 1 ≤ m ≤ 2 ⋅ 1 0 5 ) m(1≤m≤2⋅10 ^5) m(1≤m≤2⋅105)条边的有向图，边权都有正有负，求 s s s 到 t t t 的最短路，保证 s s s 到 t t t 之间至少存在一条路。

  • 如果 s s s 到 t t t 的路径可以无穷小，输出 − I N F - INF −INF

专门用一个数组存从 s s s 到 v v v 经过的点的数量，如果经过的点的数量大于 n n n 就证明有负环

——代码如下 ：

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int Min = 0;
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++) {
		int u1, v1, w1;
		cin >> u1 >> v1 >> w1;
		add_edge(u1, v1, w1);
	}
	vector<int> dj(m + 1, 200005), pd(n + 1, 0);
	dj[s] = 0, pd[s] = 1;
	priority_queue<pair<int, int>> q;
	q.push({dj[s], s});
	while (!q.empty()) {
		int k = 0, w = q.top().first, u = q.top().second;
		w = -w;
		if (pd[u] > n) {
			cout << "-INF";
			return 0;
		}
		q.pop();
		if (dj[u] != w) continue;
		for (int j = head[u]; j != -1; j = >edge[j].next) {
			int v = edge[j].v, z = dj[u] + edge[j].w;
			if (dj[v] > z) q.push({-(dj[v] = z), v}), >pd[v] = pd[u] + 1;
		}
		pd[u]++;
	}
	cout << dj[t];
	return 0;
}

3.P9751 [CSP-J 2023] 旅游巴士

https://www.luogu.com.cn/problem/P9751

题目描述

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 n n n 处地点，在这些地点之间连有 m m m 条道路。其中 1 1 1 号地点为景区入口， n n n 号地点为景区出口。我们把一天当中景区开门营业的时间记为 0 0 0 时刻，则从 0 0 0 时刻起，每间隔 k k k 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 1 1 1 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 k k k 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个
“开放时间” a i a _ i ai​，游客只有不早于 a i a _ i ai​ 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

输入格式

输入的第一行包含 3 个正整数 n , m , k n, m, k n,m,k，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 m m m 行，每行包含 3 个非负整数 u i , v i , a i u _ i, v _ i, a_ i ui​,vi​,ai​，表示第 i i i 条道路从地点 u i u _ i ui​ 出发，到达地点 v i v _ i vi​，道路的“开放时间”为 a i a _ i ai​。

输出格式

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

思路：

    1. d p [ i ] [ j ] dp[i][j] dp[i][j]表示从 u u u到 i i i余数为 j j j的最短路

——代码如下：

#include <bits/stdc++.h>
using namespace std;
int e = 0;
const int M = 20005, N = 10005;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add_edge(u, v, w);
	}
	vector<vector<int>> dp(n + 1, vector<int>(k, -1));
	priority_queue<tuple<int, int, int>> q;
	dp[1][0] = 0;
	q.push({0, 1, 0});
	while (!q.empty()) {
		auto [w, u, xj] = q.top();
		q.pop();
		w = -w;

		if (w != dp[u][xj]) continue;
		for (int j = head[u]; j != -1; j = edge[j].next) {
			int w1 = w + 1, w2 = w + (edge[j].w - w + k - 1) / k * k + 1, v = edge[j].v;
			int xk = w1 % k, yk = w2 % k;
			if (w >= edge[j].w) {
				if (dp[v][xk] == -1 or dp[v][xk] > w1) q.push({-(dp[v][xk] = w1), v, xk});
			} else if (dp[v][yk] == -1 or dp[v][yk] > w2) q.push({-(dp[v][yk] = w2), v, yk});
		}
	}
	cout << dp[n][0];
	return 0;
}

// int w2 = w + (edge[j].w - w + k - 1) / k * k + 1

4.有边数限制的最短路

https://www.acwing.com/problem/content/855/

题目：

  • 给定一个 n n n 个点 m m m 条边的 有向图，图中可能存在重边和自环， 边权可能为负数。
  • 请你求出从 1 号点到 n n n 号点的 最多经过 k 条边 的最短距离，如果无法从 1 号点走到 n n n 号点，输出 i m p o s s i b l e 。 impossible。 impossible。

注意：图中可能 存在负权回路 。

——代码：

#include <bits/stdc++.h>
using namespace std;
const int M = 10005, INF = 1000000000;
struct Edge {
	int x, y, z, next;
} edge[M];
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> head(n + 1, -1);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		edge[i].x = x;
		edge[i].y = y;
		edge[i].z = z;
		edge[i].next = head[x];
		head[x] = i;
	}
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
	priority_queue<tuple<int, int, int>> q;
	dp[1][0] = 0;
	q.push({-dp[1][0], 1, 0});
	for (int i = 1; i <= k; i++) {
		for (int u = 1; u <= n; u++) {
			for (int j = head[u]; j != -1; j = edge[j].next) {
				int v1 = edge[j].y, temp = edge[j].z + dp[u][i - 1];
				if (temp < dp[v1][i]) dp[v1][i] = temp;
			}
		}
	}
	int minsum = INF;
	for (int i = k; i >= 1; i--) {
		minsum = min(minsum, dp[n][i]);
	}
	if (minsum <= 5000000) {
		cout << minsum << '\n';
		return 0;
	}
	cout << "impossible" << '\n';
	return 0;
}

最多更新 k k k次，所以可以不用队列优化，直接枚举即可。

5.求任意2点间最短路

题目：

  • 给定一个 n 个点 m 条边的 有向图，图中可能存在重边和自环，边权可能为负数。
  • 再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 i m p o s s i b l e impossible impossible。

这题用 F l o y d Floyd Floyd 即可， 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int main() {
	int n, m, t;
	cin >> n >> m >> t;
	vector<vector<int>> dj(n + 1, vector<int> (n + 1, INF));
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		dj[u][v] = min(dj[u][v], w);

	}
	for (int i = 1; i <= n; i++) {
		dj[i][i] = 0;
	}
	for (int k = 1; k <= n; k++) {
		for (int u = 1; u <= n; u++) {
			for (int v = 1; v <= n; v++) {
				if (u == k || u == v || k == v) continue;
				dj[u][v] = min(dj[u][v], dj[u][k] + dj[k][v]);
			}
		}
	}
	const int PD = 200000005;
	while (t--) {
		int u, v;
		cin >> u >> v;
		if (dj[u][v] < PD) cout << dj[u][v] << '\n';
		else cout << "impossible" << '\n';
	}
	return 0;
}

6.聚会

原题链接：https://www.acwing.com/problem/content/5478/

题目：

  • 约翰的农场有 n n n 个谷仓，编号 1 ∼ n 1∼n 1∼n，谷仓之间有 m m m 条双向道路。

  • 所有道路的长度均为 1。

  • 奶牛们可以通过这些道路从任意谷仓到达任意其它谷仓。

  • 任意两个谷仓之间最多只包含一条道路（注意是道路，不是路径）。

  • 不存在道路两端都连接同一个谷仓的情况。

  • 农场中一共有 k k k 种干草，编号 1 ∼ k 1∼k 1∼k。

  • 每个谷仓都存有一种干草，其中第 i i i 个谷仓存有第 a i a_i ai​种干草。

  • 每种干草都至少存在于一个谷仓中。

  • 奶牛们计划选择一个谷仓举办干草宴会。为了让宴会足够丰盛，至少需要将 s s s 种不同的干草汇集在宴会谷仓。

  • 宴会谷仓本身就包含一种干草，而其它干草就需要从其它谷仓运输。

已知，将一种干草从一个谷仓运至另一个谷仓所需的运输成本等于两谷仓之间的最短路径距离。
请你帮助奶牛们计算，对于每个谷仓，如果挑选其为宴会举办地，则举办宴会需要付出的总运输成本的最小可能值是多少。

思路：
dp[i][k] 表示从点 i i i到第 k k k种粮食的最短路
——代码如下 ：

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int n, m, k, s; //n 个谷仓 , m 条路 , k种干草 ,需要 s 种干草
	cin >> n >> m >> k >> s;
	vector<int> a1(n + 1, 0);// 第 i 个稻谷存的种类
	vector<vector<int>> c(k + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a1[i];
		c[a1[i]].push_back(i);// 第 i 种稻谷存在了哪几个谷仓里
	}
	for (int i = 0; i < m; i++) {
		int u, v, w = 1;
		cin >> u >> v;
		add_edge(u, v, 1);
		add_edge(v, u, 1);
		// 运输成本为1， 因为为无向图所以输入两次边
	}
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1));
	// dp[i][k] 表示以 i 为起点到 第 k 种粮食的最短路
	for (int i = 1; i <= k; i++) {
		int ans = 0;
		priority_queue<tuple<int, int, int>> q;
		for (int k = 0; k < c[i].size(); k++) {
			q.push({-(dp[c[i][k]][i] = 0), c[i][k], i});
			// 起点到自己的距离为0
		}
		while (!q.empty()) {
			auto [w, u, k2] = q.top();
			q.pop();
			w = -w;
			if (w != dp[u][k2]) continue;
			for (int j = head[u]; j != -1; j = edge[j].next) {
				int temp = w + 1;
				int v1 = edge[j].v;
				if (dp[v1][k2] == -1 || dp[v1][k2] > temp) q.push({-(dp[v1][k2] = temp), v1, k2});
			}
		}
		//spfa算法
	}
	for (int i = 1; i <= n; i++) {
		sort(dp[i].begin() + 1, dp[i].end());
		int ans = 0;
		for (int j = 1; j <= s; j++) {
			ans += dp[i][j];
		}
		cout << ans << " ";
		//计算前s条路的最短路和
	}
	return 0;
}

7.最小边权最大的路径

原题链接：https://vijos.org/p/1391

题目：

  • 小衫困在某个监狱，监狱是由 n n n 个小房间和 m m m 条小房间之间的单向的管道组成的。
  • 对于某个管道，小杉只能在人品不超过一定程度时通过。
  • 小杉一开始在房间 1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。

注意，小杉的人品在出发以后是不会改变的。

思路：
只需要在 S P F A SPFA SPFA的基础上改变 , 把用作比较的“ t e m p temp temp”改为“ t e m p = m i n ( r , e d g e [ i ] . r ) temp = min(r, edge[i].r) temp=min(r,edge[i].r)” 就可以了

——代码如下 :

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, r, next;
} edge[M];
void add_edge(int u, int v, int r) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].r = r;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, r;
		cin >> u >> v >> r;
		add_edge(u, v, r);
	}
	vector<int> dp(n + 1, -1);
	priority_queue<pair<int, int>> q;
	dp[1] = 1000000005;
	q.push({dp[1], 1});
	while (!q.empty()) {
		auto [r, u] = q.top();
		q.pop();
		if (r != dp[u]) continue;
		for (int i = head[u]; i != -1; i = edge[i].next) {
			int u1 = edge[i].u, v = edge[i].v, r1 = edge[i].r;
			int temp = min(r, edge[i].r);
			if (dp[v] == -1 || temp > dp[v]) q.push({dp[v] = temp, v});
		}
	}
	for (int i = 2; i <= n; i++) {
		cout << dp[i] << '\n';
	}
	return 0;
}

8.最小费用

题目 ：

  • 给定平面上的 n 个点，定义点 ( x 1 , y 1 ) (x_1 , y_1) (x1​,y1​) 到点 ( x 2 , y 2 ) (x_2 , y_2) (x2​,y2​) 的费用为 m i n ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ ) min(|x_1 - x_2| , |y_1 - y_2|) min(∣x1​−x2​∣,∣y1​−y2​∣) 。

求从 1 号点走到 n 号点的最小费用。

思路：

这题并不需要任意两个点之间都建边，只需要排序后按 x x x 坐标和 y y y 坐标建就可以了,因为第 x x x 坐标 i i i 小的点的离他最近的点一定是 x x x 坐标第 ( i − 1 ) (i - 1) (i−1) 小的点。

——代码如下 ：

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int n;
	cin >> n;
	vector<int> xa(n + 1, 0), ya(n + 1, 0);
	vector<pair<int, int>> x(n + 1, {0, 0}), y(n + 1, {0, 0});
	for (int i = 1; i <= n; i++) {
		cin >> x[i].first >> y[i].first;
		x[i].second = i;
		y[i].second = i;
		xa[i] = x[i].first;
		ya[i] = y[i].first;
	}
	sort(x.begin() + 1, x.end());
	sort(y.begin() + 1, y.end());
	for (int i = 1; i < n; i++) {
		int xa1 = -xa[x[i].second] + xa[x[i + 1].second];
		add_edge(x[i].second, x[i + 1].second, xa1);
		add_edge(x[i + 1].second, x[i].second, xa1);
	}
	for (int i = 1; i < n; i++) {
		int ya1 = -ya[y[i].second] + ya[y[i + 1].second];
		add_edge(y[i].second, y[i + 1].second, ya1);
		add_edge(y[i + 1].second, y[i].second, ya1);
	}
	vector<int> dp(n + 1, -1);
	priority_queue<pair<int, int>> q;
	dp[1] = 0;
	q.push({dp[1], 1});
	while (!q.empty()) {
		auto [w, u] = q.top();
		q.pop();
		w = -w;
		if (w != dp[u]) continue;
		for (int j = head[u]; j != -1; j = edge[j].next) {
			int v = edge[j].v, w1 = edge[j].w;
			int temp = w + w1;
			if (dp[v] == -1 || temp < dp[v]) q.push({-(dp[v] = temp), v});
		}
	}
	cout << dp[n] << '\n';
	return 0;
}

9.飞行路线

原题网址：https://www.luogu.com.cn/problem/P4568

题目 ：

  • Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 n n n 个城市设有业务，设这些城市分别标记为 0 0 0 到 n − 1 n-1 n−1，一共有 m m m 种航线，每种航线连接两个城市，并且航线有一定的价格。

  • Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 k k k 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？

思路：

  • dp[i][j] 表示从点s出发到点i的还剩j次免费转乘机会的最短路

——代码如下 ：

#include <bits/stdc++.h>
#define repe(j, k) for(int j=head[k];j!=-1;j=edge[j].next)
using namespace std;
const int M = 200005, N = 100005;
int e = 0;
vector<int> head(N, -1);
struct Edge {
	int u, v, w, next;
} edge[M];
void add_edge(int u, int v, int w) {
	edge[e].u = u;
	edge[e].v = v;
	edge[e].w = w;
	edge[e].next = head[u];
	head[u] = e++;
}
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	// 分别表示城市数，航线数和免费乘坐次数。
	int s, t;
	cin >> s >> t;
	//从城市s出发到城市t
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
		//无向图
	}
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1));
	priority_queue<tuple<int, int, int>> q;
	dp[s][k] = 0;
	// dp[i][j] 表示从点s出发到点i的还剩j次免费转乘机会的最短路
	q.push({dp[s][k], s, k});
	while (!q.empty()) {
		auto [w, u, k1] = q.top();
		q.pop();
		w = -w;
		if (w != dp[u][k1]) continue;
		for (int j = head[u]; j != -1; j = edge[j].next) {
			int v = edge[j].v, w1 = edge[j].w;
			int temp = w + w1, temp1 = w;

			if (dp[v][k1] == -1 || temp < dp[v][k1] ) {
				q.push({-(dp[v][k1] = temp), v, k1});
			}
			if ((k1 - 1) >= 0 && (dp[v][k1 - 1] == -1 || temp1 < dp[v][k1 - 1]) ) {
				q.push({-(dp[v][k1 - 1] = temp1), v, k1 - 1});
			}
		}
	}
	//SPFA
	sort(dp[t].begin(), dp[t].end());
	cout << dp[t][0];
	return 0;
}

——图的存储与最短路算法完

标签：存储,dj,int,短路,head,next,算法,edge,dp
From： https://blog.csdn.net/weixin_54990292/article/details/141474448

相关文章

  • 基于模拟退火算法求解物流选址问题(附word文档)
    基于模拟退火算法求解物流选址问题(附word文档)......
  • 003.DirectPV存储管理
    目录DirectPVdrives管理先决条件添加drives列出drives标记drives替换drives移除drives暂停drives修复drives扩容Volume在线扩容删除Volume清理残留Volume暂停VolumeDirectPVdrives使用使用介绍创建PVC创建PodDirectPVdrives管理先决条件已安装DirectPV插件。在Kubernetes......
  • SPFA算法
    1.spfa求最短路给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数n和m。接下来m行每行包含三个整数x,y,z，表......
  • 算法总结-树链剖分
    算法总结-树链剖分概念重儿子（红点）：父节点\(f\)的子节点中子树大小最大的儿子。轻儿子（蓝点）：父节点\(f\)的子节点中除重儿子以外的节点。重链（橙圈框出的链）：链顶为轻儿子，由重儿子组成的链。重链剖分用处：将树上任意一条路径划分成不超过\(\log{n}\)条连续的链（如实......
  • 机器学习—KNN算法-分类及模型选择与调优
    KNN算法-分类样本距离判断：欧氏距离、曼哈顿距离、明可夫斯基距离KNN算法原理：        K-近邻算法（K-NearestNeighbors，简称KNN）,根据K个邻居样本的类别来判断当前样本的类别;如果一个样本在特征空间中的k个最相似(最邻近)样本中的大多数属于某个类别，......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（10）
    时间：08_181011NOI2024 31.80%(703/2211)1008SunBian 55.02%(669/1216)1009不基本子串结构 20.57%(589/2864)1002scenery 21.00%(368/1752)1011NOI2024思路题目问的是“是否一定”，考虑最差情况，比自己排名高的全部拿分了，剩下的人一分不拿，与自己并列排名最后每场......
  • 最短路
    这是仙人掌的模板题，仙人掌不能有自环，但是可以有重边。多颗仙人掌组成的图叫做沙漠。将仙人掌的每个环缩成一个点之后，就会形成树仙人掌转树要利用圆方树：①.任选一个点为根②.此时每个环有且仅有唯一一个点到根的距离最近。然后将环中的点分类，离根节点最近的点叫“头”，剩余的点作......
  • 代码随想录算法训练营第 50 天 |98. 所有可达路径
    代码随想录算法训练营Day50代码随想录算法训练营第50天|98.所有可达路径目录代码随想录算法训练营前言LeetCode98.所有可达路径一、图论基础概念1、图的种类2、度3、连通性：节点的连通情况4、图的构造5、图的遍历方式二、深度优先搜索1、深度优先搜索的三部曲2......
  • 代码随想录算法训练营第 51 天 |LeetCode99岛屿数量 LeetCode100.岛屿的最大面积
    代码随想录算法训练营Day51代码随想录算法训练营第51天|LeetCode99岛屿数量LeetCode100.岛屿的最大面积目录代码随想录算法训练营前言LeetCode200岛屿数量LCR105.岛屿的最大面积一、广度优先搜索基础1、用队列实现2、代码框架：二、卡码网99岛屿数量（LeetCode......
  • 代码随想录算法训练营第 49 天 |LeetCode42 接雨水 LeetCode84 柱状图中最大面积矩形
    代码随想录算法训练营Day49代码随想录算法训练营第49天|LeetCode42接雨水LeetCode84柱状图中最大面积矩形目录代码随想录算法训练营前言LeetCode42接雨水LeetCode84柱状图中最大面积矩形一、LeetCode42接雨水1.题目链接2.思路3.题解二、LeetCode84柱状......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99