（课设第一套）1-5 317号子任务 (100 分)（Dijkstra:重边自环）

题目

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