c++新年好和通信路线(acwing)

2023-10-24 20:46

本文主要是介绍c++新年好和通信路线(acwing),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第一个问题在于枚举

先看题目:

重庆城里有 n个车站,m 条 双向 公路连接其中的某些车站。

每两个车站最多用一条公路连接,从任何一个车站出发都可以经过一条或者多条公路到达其他车站,但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 11,他有五个亲戚,分别住在车站 a,b,c,d,e。

过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。

怎样走,才需要最少的时间?

输入格式

第一行:包含两个整数 n,m,分别表示车站数目和公路数目。

第二行:包含五个整数 a,b,c,d,e,分别表示五个亲戚所在车站编号。

以下 m 行,每行三个整数 x,y,t,表示公路连接的两个车站编号和时间。

输出格式

输出仅一行,包含一个整数 T,表示最少的总时间。

数据范围

1≤n≤50000,
1≤m≤10^5,
1<a,b,c,d,e≤n,
1≤x,y≤n,
1≤t≤100

输入样例:
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

输出样例:

21

代码如下

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>using namespace std;typedef pair<int, int> PII;
const int N = 5e4 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;int n, m;
int h[N], w[M], e[M], ne[M], idx;
int source[N];
int dist[6][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(int start, int dist[])
{memset(dist, 0x3f, N * 4);//因为这边传过来的数组,实际是指针,所以是N*4memset(st, 0, sizeof st);dist[start] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, start});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second;if(st[ver]) continue;st[ver] = true;for(int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];heap.push({dist[j], j});}}}
}// 枚举每种拜访次序,求出最小距离
// 拜访了u个人,自己是第1个人;当前起点是source[start],当前走过的距离是distance
int dfs(int u, int start, int distance)
{if(u > 5) return distance;//走完了,返回// res存距离最短的分支int res = INF;for(int i = 1; i < 6; i ++){if(!st[i]){int next = source[i];//走亲戚st[i] = true;res = min(res, dfs(u + 1, i, distance + dist[start][next]));st[i] = false;}}return res;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);source[0] = 1;//第一个结点为1for(int i = 1;i <= 5; i ++) cin >> source[i];//输入剩余五个亲戚的站台号while(m --){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}for(int i = 0; i < 6; i ++) dijkstra(source[i], dist[i]);//每一个节点都跑一次最短路memset(st, 0, sizeof st);//重置st数组,因为要再次使用cout << dfs(1, 0, 0) << endl;//输出答案return 0;
}

第二个题目:

博主用的分层图做法

先看题目:

在郊区有 N 座通信基站,P条 双向 电缆,第 i 条电缆连接基站 Ai 和 Bi。

特别地,11 号基站是通信公司的总站,N 号基站位于一座农场中。

现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li。

电话公司正在举行优惠活动。

农产主可以指定一条从 11 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 11 行:三个整数 N,P,K。

第 2..P+1 行:第 i+1 行包含三个整数 Ai,Bi,Li。

输出格式

包含一个整数表示最少花费。

若 11 号基站与 N 号基站之间不存在路径,则输出 −1−1。

数据范围

0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000

代码如下:

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>using namespace std;typedef pair<int, int> PII;
//因为建议k层分层图,所以数据是这样的
const int N = 1e6 + 10, M = 2e7 + 10, INF = 0x3f3f3f3f;int n, m, k;
int h[N], w[M], e[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;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if(st[ver]) continue;st[ver] = true;for(int i = h[ver]; ~ i; i = ne[i]){int j = e[i], x = max(dist[ver], w[i]);//这里是比较价格最大的那个if(dist[j] > x){dist[j] = x;heap.push({dist[j], j});}}}
}int main()
{cin >> n >> m >> k;memset(h, -1, sizeof h);while(m --){int a, b, c;scanf("%d%d%d",&a, &b, &c);add(a, b, c), add(b, a, c);for(int j = 1; j <= k; j ++)//k次免费,建议k层分层图{add(j * n + a, j * n + b, c);add(j * n + b, j * n + a, c);add((j - 1) * n + a, j * n + b, 0);add((j - 1) * n + b, j * n + a, 0);}}//给每层终点建一条边是为了防止出现用不到k次就出现最短路的情况for(int i = 1; i <= k; i ++) add(i * n, (i + 1) * n, 0);dijkstra();if(dist[(k + 1) * n] == INF) puts("-1");else cout <<dist[(k + 1) * n] << endl;return 0;
}

明白的小伙伴麻烦点个赞吧

这篇关于c++新年好和通信路线(acwing)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/277668

相关文章

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(