当前位置:网站首页>(课设第一套)1-5 317号子任务 (100 分)(Dijkstra:重边自环)
(课设第一套)1-5 317号子任务 (100 分)(Dijkstra:重边自环)
2022-07-06 09:18:00 【劲腰傩舞】
题目
1-5 317号子任务 (100 分)
背景:
“你在平原上走着走着,突然迎面遇到一堵墙,这墙向上无限高,向下无限深,向左无限远,向右无限远,这墙是什么?”——《流浪地球》原著
我们带着地球去流浪了,为了处理流浪过程中可能会发生的危机,联合政府找到你,希望你能协助完成 317 号子任务:制定应急预案。
题目:
地球的表面有 n 个据点,这些据点之间存在 m 条双向道路。
这些据点中,有的是建立在行星发动机之下,受到行星发动机的保护(行星发动机据点),而其他据点则没有行星发动机的保护(普通据点,比如燃料采集据点/科研据点等)。
当发生危机的时候,没有行星发动机的保护是非常危险的,所以每个人都需要赶到最近的行星发动机据点寻求庇护,然而行星发动机据点也不一定安全,再加上行星发动机据点容量有限,所以有些时候得去第二近或者第三近的行星发动机据点。
联合政府找到你,希望你能够计算出每个据点最近的 k 个行星发动机据点,为了简化问题,你只需要输出每个据点到最近 k 个行星发动机据点的最短距离之和,如果某个据点能够到达的行星发动机据点不足 k 个,则输出其能到达的所有行星发动机的最短距离之和。
输入格式:
从标准输入读入数据。
输入的第一行包含三个用空格隔开的整数 n, m, k ,含义见题目描述,保证 1 ≤ n ≤10^4, 0 ≤ m ≤ 10^4, 1 ≤ k ≤ 10^2。据点依次编号为 1 到 n 。
第二行包含 n 个整数依次表示每个据点的类型,每个数为 1 或 0 (1 表示对应据点为行星发动机据点,0 表示普通据点)。
接下来 m 行,每行三个整数 u, v,w 表示有一条长度为 w 的双向道路连接 u 号据点和 v 号据点,1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^3 。
可能有重边和自环。
输出格式:
输出到标准输出。
输出 n 行,每行输出一个整数表示答案(见题目描述)。
输入样例:
7 6 2
1 0 1 0 1 1 0
1 4 1
1 2 3
2 4 4
2 3 5
2 5 7
6 7 5
输出样例:
8
8
8
10
10
0
5
作者
景荣
单位
燕山大学
代码长度限制
16 KB
时间限制
1000 ms
内存限制
512 MB
思路
刚开始主要在纠结
什么是重边?
什么是自环?
这俩货对这题有啥影响?
没办法
才刷题一个月
知道的很少
重边就是两点之间的距离多次赋值
所以输入的时候
可能被覆盖
注意一下就行
自环就是自己到自己的边
图初始化完成之后
再把graoh[i][i]设为无穷大就好了
那如何用dijkstra找到某个点最近的k个据点?
注意这k个据点可以包含自己
只需要用dijksra计算出dis数组后
对dis数组进行遍历
找到最小的,并且是据点的点
当然
因为dijkstra每次循环的时候都可以找出dis最小的那点个
所以顺便取出存在一个数组中就可以了
另外
注意一下八次dijkstra的数据的独立性就行
就是说
不能公用dis和visited数组
年级大佬是用priority_queue来优化dijkstra的,嗯嗯好好学
代码
using namespace std;
#include<bits/stdc++.h>
int graph[10010][10010], dis[10010], visited[10010], tank[10010], a, b, c;
int n, m, k;
void dijkstra(int a) {
memset(visited, 0, sizeof visited);//独立初始化
memset(dis, 0x3f, sizeof dis);//独立初始化
int cnt = k;//cnt个目的地,可包含自己
int result = 0;
dis[a] = 0;
vector<int>path;
for (int i = 0; i < n ; i++) {
int min = 0x3f3f3f3f, minid = -1;
for (int j = 1; j <= n; j++) {
if (dis[j] < min && !visited[j]) {
min = dis[j];
minid = j;
}
}
if (minid == -1)break;
visited[minid] = 1;
path.push_back(minid);
for (int k = 1; k <= n; k++) {
if (!visited[k] && dis[k] > dis[minid] + graph[minid][k])
dis[k] = dis[minid] + graph[minid][k];
}
}
for (int i = 0; i < path.size(); i++) {
if (!cnt)break;
if (dis[path[i]]!=0x3f3f3f3f&&tank[path[i]]) {
cnt--;
result += dis[path[i]];
}
}
cout << result << endl;
}
int main() {
memset(graph, 0x3f, sizeof graph);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) //n个点,tank判断是否据点
cin >> tank[i];
for (int i = 1; i <= m; i++) {
//m条边
cin >> a >> b >> c;
graph[a][b] = graph[b][a] = c <= graph[a][b] ? c : graph[a][b];//重边
}
for (int i = 1; i <= n; i++) //自环
graph[i][i] = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) //各来一遍
dijkstra(i);
return 0;
}
边栏推荐
- Redis cache update strategy, cache penetration, avalanche, breakdown problems
- Common properties of location
- Detailed explanation of truncate usage
- Esp8266 connect onenet (old mqtt mode)
- open-mmlab labelImg mmdetection
- GCC compilation options
- Mysqldump error1066 error solution
- JS variable types and common type conversions
- Servlet
- Stm32f1+bc20+mqtt+freertos system is connected to Alibaba cloud to transmit temperature and humidity and control LED lights
猜你喜欢
ESP8266连接onenet(旧版MQTT方式)
AMBA、AHB、APB、AXI的理解
Walk into WPF's drawing Bing Dwen Dwen
ES6 grammar summary -- Part 2 (advanced part es6~es11)
Basic operations of databases and tables ----- modifying data tables
Fashion Gen: the general fashion dataset and challenge paper interpretation & dataset introduction
单片机蓝牙无线烧录
Missing value filling in data analysis (focus on multiple interpolation method, miseforest)
Vulnhub target: hacknos_ PLAYER V1.1
Arm pc=pc+8 is the most understandable explanation
随机推荐
Redis 缓存更新策略,缓存穿透、雪崩、击穿问题
关于Gateway中使用@Controller的问题
[offer18] delete the node of the linked list
History object
Latex learning
基于Redis的分布式锁 以及 超详细的改进思路
Imgcat usage experience
Important methods of array and string
Priority inversion and deadlock
Amba, ahb, APB, Axi Understanding
Arduino gets the length of the array
JS variable types and common type conversions
MySQL time, time zone, auto fill 0
Talking about the startup of Oracle Database
@The difference between Autowired and @resource
level16
CUDA C programming authoritative guide Grossman Chapter 4 global memory
Use of lists
RT thread API reference manual
Walk into WPF's drawing Bing Dwen Dwen