(the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)

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;
}