2023河南萌新联赛第（三）场：郑州大学（两个题目）

**2023年河南萌新联赛第（三）场：郑州大学**

在本场比赛中，我们将挑战两道题目，分别是：

1. **题目一：**
- 题目描述：
在一个由 $n$ 个点组成的图中，每个点都有一个权值。我们需要找到两个相邻点之间的最小距离。
- 输入格式：
第一行：$n$
第二行：$n$ 个点的坐标 $(x_i, y_i)$ 第三行：每个点的权值 $w_i$
- 输出格式：
一个整数，表示两个相邻点之间的最小距离。

2. **题目二：**
- 题目描述：
给定一个由 $n$ 个点组成的图，每个点都有一个权值。我们需要找到一个子图，使得每个点的度数至少为3，并且这个子图中所有点的权值之和最大。
- 输入格式：
第一行：$n$
第二行：$n$ 个点的坐标 $(x_i, y_i)$ 第三行：每个点的权值 $w_i$
- 输出格式：
一个整数，表示子图中所有点的权值之和。

**题目一：**

### 题解我们可以使用 Dijkstra 算法来解决这个问题。首先，我们需要构建一个邻接矩阵来存储每个点之间的距离，然后使用 Dijkstra 算法找到两个相邻点之间的最小距离。

import sysfrom heapq import heappop, heappushdef dijkstra(graph, start):
 # 初始化距离和前驱节点 distance = [sys.maxsize] * len(graph)
 predecessor = [-1] * len(graph)

 # 初始化优先队列 pq = [(0, start)]

 while pq:
 current_distance, current_node = heappop(pq)

 if current_distance > distance[current_node]:
 continue for neighbor, weight in enumerate(graph[current_node]):
 if weight ==0:
 continue new_distance = current_distance + weight if new_distance < distance[neighbor]:
 distance[neighbor] = new_distance predecessor[neighbor] = current_node heappush(pq, (new_distance, neighbor))

 return distance, predecessordef find_min_distance(graph):
 n = len(graph)
 min_distance = sys.maxsize for i in range(n):
 for j in range(i +1, n):
 if graph[i][j] !=0:
 min_distance = min(min_distance, graph[i][j])

 return min_distancedef solve():
 n = int(input())
 points = [tuple(map(int, input().split())) for _ in range(n)]
 weights = list(map(int, input().split()))

 # 构建邻接矩阵 graph = [[0] * n for _ in range(n)]

 for i in range(n):
 for j in range(i +1, n):
 distance = ((points[i][0] - points[j][0]) **2 +
 (points[i][1] - points[j][1]) **2) **0.5 graph[i][j] = graph[j][i] = int(distance)

 min_distance = find_min_distance(graph)
 print(min_distance)


solve()

import sysdef solve():
 n = int(input())
 points = [tuple(map(int, input().split())) for _ in range(n)]
 weights = list(map(int, input().split()))

 # 初始化度数和前驱节点 degree = [0] * n predecessor = [-1] * n # 初始化子图中所有点的权值之和 total_weight =0 for i in range(n):
 if degree[i] >=3:
 continue # 找到一个点，将其连接到其他所有点上 for j in range(i +1, n):
 if degree[j] < 3:
 degree[i] +=1 degree[j] +=1 predecessor[i] = j predecessor[j] = i # 计算子图中所有点的权值之和 total_weight += weights[i]

 print(total_weight)


solve()