当前位置:网站首页>(the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)
(the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)
2022-07-06 12:33:00 【Vigorous waist Nuo dance】
subject
1-5 317 Sub mission (100 branch )
background :
“ You walk on the plain , Suddenly I met a wall head-on , The wall is infinitely high up , Down to infinity , Left infinity , Right infinity , What is this wall ?”——《 Wandering the earth 》 The original
We took the earth to wander , In order to deal with the possible crisis in the process of wandering , The coalition found you , I hope you can help to complete 317 Sub mission : Make emergency plan .
subject :
The surface of the earth has n A stronghold , Between these strongholds m Two way road .
In these strongholds , Some are built under planetary engines , Protected by planetary engines ( Planetary engine stronghold ), Other strongholds are not protected by planetary engines ( Common stronghold , Like fuel collection sites / Scientific research base, etc ).
When there's a crisis , It's very dangerous without the protection of planetary engines , So everyone needs to go to the nearest planetary engine base for shelter , However, planetary engine sites are not necessarily safe , Plus the limited capacity of the planetary engine base , So sometimes you have to go to the second or third nearest planetary engine base .
The coalition found you , I hope you can calculate the nearest k A planetary engine base , To simplify the problem , You just need to export each site to the nearest k The sum of the shortest distances between two planetary engine sites , If there are not enough planetary engine sites that a site can reach k individual , Then output the sum of the shortest distance of all planetary engines it can reach .
Input format :
Reading data from standard input .
The first line of input contains three integers separated by spaces n, m, k , The meaning is shown in the title description , Guarantee 1 ≤ n ≤10^4, 0 ≤ m ≤ 10^4, 1 ≤ k ≤ 10^2. The strongholds are numbered as 1 To n .
The second line contains n An integer represents the type of each site in turn , Each number is 1 or 0 (1 Indicates that the corresponding site is a planetary engine site ,0 It means a common stronghold ).
Next m That's ok , Three integers per row u, v,w It means that there is a length of w Two way road connection u Base number and v No. 1 stronghold ,1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^3 .
There may be double edges and self rings .
Output format :
Output to standard output .
Output n That's ok , Each line outputs an integer to represent the answer ( See Title Description ).
sample input :
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
sample output :
8
8
8
10
10
0
5
author
Jingrong
Company
Yanshan University
Code length limit
16 KB
The time limit
1000 ms
Memory limit
512 MB
Ideas
At first, I was mainly struggling
What is heavy edge ?
What is a self ring ?
What effect do these two goods have on this problem ?
Can't
I've only been writing questions for a month
Know very little
The double edge is the multiple assignment of the distance between two points
So when typing
May be covered
Just pay attention
Self ring is to get to your side
Figure after initialization
And then graoh[i][i] Set it to infinity
How to use dijkstra Find the nearest point k A stronghold ?
Pay attention to this k A stronghold can contain itself
Only need to use dijksra To calculate the dis After array
Yes dis Array traversal
Find the smallest , And it's a stronghold
Of course
because dijkstra You can find it every time you cycle dis The smallest one
So by the way, it's OK to take it out and store it in an array
in addition
Pay attention eight times dijkstra The independence of data is ok
That is to say
Not for public use dis and visited Array
Grade leaders use priority_queue To optimize dijkstra Of , Uh huh, study hard
Code
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);// Independent initialization
memset(dis, 0x3f, sizeof dis);// Independent initialization
int cnt = k;//cnt Destination , Include yourself
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 A little bit ,tank Determine whether the stronghold
cin >> tank[i];
for (int i = 1; i <= m; i++) {
//m side
cin >> a >> b >> c;
graph[a][b] = graph[b][a] = c <= graph[a][b] ? c : graph[a][b];// Heavy edge
}
for (int i = 1; i <= n; i++) // Self ring
graph[i][i] = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) // Come once each
dijkstra(i);
return 0;
}
边栏推荐
- Compilation principle: preprocessing of source program and design and implementation of lexical analysis program (including code)
- Intermediate use tutorial of postman [environment variables, test scripts, assertions, interface documents, etc.]
- Minio文件下载问题——inputstream:closed
- [Offer18]删除链表的节点
- MySQL takes up too much memory solution
- (四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
- Minio file download problem - inputstream:closed
- PT OSC deadlock analysis
- JS正则表达式基础知识学习
- VIM command line notes
猜你喜欢
JS function promotion and declaration promotion of VaR variable
JS数组常用方法的分类、理解和运用
ES6 grammar summary -- Part I (basic)
数据库课程设计:高校教务管理系统(含代码)
编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
Walk into WPF's drawing Bing Dwen Dwen
Basic operations of databases and tables ----- view data tables
[esp32 learning-1] construction of Arduino esp32 development environment
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
随机推荐
Arduino get random number
level16
E-commerce data analysis -- salary prediction (linear regression)
Redis based distributed locks and ultra detailed improvement ideas
[leetcode622]设计循环队列
js题目:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。
(4) Data visualization of R language -- matrix chart, histogram, pie chart, scatter chart, linear regression and strip chart
ES6 grammar summary -- Part 2 (advanced part es6~es11)
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
编译原理:源程序的预处理及词法分析程序的设计与实现(含代码)
ES6语法总结--下篇(进阶篇 ES6~ES11)
如何给Arduino项目添加音乐播放功能
VIM command line notes
程序设计大作业:教务管理系统(C语言)
JS variable types and common type conversions
Solution to the problem of automatic login in Yanshan University Campus Network
Gateway 根据服务名路由失败,报错 Service Unavailable, status=503
Arduino JSON data information parsing
Vulnhub target: hacknos_ PLAYER V1.1
js 变量作用域和函数的学习笔记