IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> [离散化][倍增][floyd变形]牛站 AcWing345 -> 正文阅读

[数据结构与算法][离散化][倍增][floyd变形]牛站 AcWing345

?给定一张由?T?条边构成的无向图,点的编号为 1~1000?之间的整数。

求从起点?S?到终点?E?恰好经过?N?条边(可以重复经过)的最短路。

注意: 数据保证一定有解。

输入格式

第?1?行:包含四个整数 N,T,S,E。

第 2..T+1?行:每行包含三个整数,描述一条边的边长以及构成边的两个点的编号。

输出格式

输出一个整数,表示最短路的长度。

数据范围

2≤T≤100,
2≤N≤10^6

输入样例:

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例:

10

题意:? 给出一张包含n个点m条边的无向图,求从s到t恰好经过T条边的最短路。

分析:? 这道题可以用类似floyd的思想处理,假如已经得到了从i到j恰好经过T-1条边的最短路(任取t小于T),那从i到j恰好经过T条边就可以通过枚举中间点k来求得。所以可以用四重循环解决,最外层枚举恰好经过的边数t,内三层跑一个floyd变形,设dis[i][j]含义为在恰好经过t条边的情况下,从i点到j点的最短距离,这样有状态转移方程temp[i][j] = min(temp[i][j], dis[i][k]+mp[k][j]),dis[i][j] = temp[i][j],用temp是为了防止过程中改变dis的值。不过这种做法时间复杂度为O(T*n^3),显然会超时,于是接下来考虑优化方法。

在内层floyd的过程中,可以发现dis值的更新是存在结合律的,也就是说从i点到j点恰好经过t条边的最短路可以拆分为经过t/2和t/2条边的最短路之和,这样就有了倍增的基础,而且存在结合律就可以用快速幂来处理。实际的代码实现也是类似快速幂的,只是把快速幂中的乘法写成了一次floyd变形,时间复杂度为O(logT*n^3)。

这道题还有一些细节。关于ans数组初值设置以及dis数组(代码中为base数组)初值设置。dis数组应该初始化为只有1条边时的最短距离,特别需要注意的是到自身的dis值不能设置为0,否则就相当于每个点都引入了一条边权为0的自环,这是不符合题意的。ans数组相当于快速幂中的base^0,也就是恰好经过0条边时的最短距离,这里到自身的最短距离要置0,这是为了保证第一次遇到power为奇数的情况时能够把ans数组赋值为base数组,就像快速幂中那样。最后还需要离散化一下点,因为点的编号为1~1000,这么多点跑一次floyd就会超时,同时注意到最多只有100条边,因此必须要离散化一下。

具体代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
using namespace std;

int m, K, s, t, base[205][205], ans[205][205], temp[205][205], num; 
vector<int> alls;
struct edge
{
	int u, v, w;
}e[105];

int find(int x)
{
	return lower_bound(alls.begin(), alls.end(), x)-alls.begin()+1;
}

void mul(int (*c)[205], int (*a)[205], int (*b)[205])
{
	memset(temp, 0x3f, sizeof temp);
	for(int k = 1; k <= num; k++)//以点k为中间点 
		for(int i = 1; i <= num; i++)
			for(int j = 1; j <= num; j++)
				temp[i][j] = min(temp[i][j], a[i][k]+b[k][j]);
	memcpy(c, temp, sizeof temp);
}

signed main()
{
	cin >> K >> m >> s >> t;
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &e[i].w, &e[i].u, &e[i].v);
		alls.push_back(e[i].u);
		alls.push_back(e[i].v);
	}
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	memset(base, 0x3f, sizeof base);
	num = alls.size();//总点数 
//	这里不可以初始化到自身边权为0,否则会不断走自环 
//	for(int i = 1; i <= num; i++)
//		base[i][i] = 0;
	for(int i = 1; i <= m; i++)
	{
		int u = find(e[i].u), v = find(e[i].v), w = e[i].w;
		base[u][v] = base[v][u] = min(base[u][v], w); 
	}
	int power = K;
	//ans一开始应保存0条边的情况
	//这样初始化目的是保证第一次mul时直接把base赋值给ans 
	memset(ans, 0x3f, sizeof ans);
	for(int i = 1; i <= num; i++)
		ans[i][i] = 0;
	while(power)
	{
		if(power&1)
			mul(ans, ans, base);
		power >>= 1;
		mul(base, base, base);
	}
	s = find(s), t = find(t);
	cout << ans[s][t];
    return 0;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-03-12 17:47:47  更:2022-03-12 17:48:46 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 13:44:36-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码