打卡信奥刷题（2672）用C++实现信奥题 P2914 [USACO08OCT] Power Failure G

本文介绍了USACO竞赛题目P2914的解决方案。题目描述了一场雷暴后农场电力网的修复问题，要求计算从电线杆1到电线杆N恢复电力连接所需的最小电线长度，其中每条电线长度不超过M。使用Dijkstra算法计算最短路径，考虑了现有电线和可新建电线的情况。C++实现通过优先队列优化，处理坐标距离计算和最短路径求解，最终输出所需长度的1000倍整数或-1（无法连接）。代码使用邻接矩阵存储距离，时间复杂度为

rogeliu

893人浏览 · 2026-01-11 07:20:00

rogeliu · 2026-01-11 07:20:00 发布

P2914 [USACO08OCT] Power Failure G

题目描述

一场猛烈的雷暴摧毁了农场电力网的一些电线！农夫约翰有一张所有 $N$ 根电线杆的地图（ $\le N \le 1000$ ），这些电线杆被方便地编号为 $1…N1\ldots N$ ，并位于整数平面坐标 $x_i, y_i)$ 上（ $\le x_i \le 100000, -100000 \le y_i \le 100000$ ）。

有 $W$ 根电线（ $\le W \le 10000$ ）连接成对的电线杆 $P_i$ 和 $P_j$ （ $\le P_i \le N, 1 \le P_j \le N$ ）。

他需要从电线杆 $1$ 获取电力到电线杆 $N$ （这意味着一些电线可以从电线杆 $1$ 通过某些中间电线杆传输到电线杆 $N$ ）。

给定 $N$ 根电线杆的位置和剩余电线的列表，确定恢复电力连接所需的最小电线长度，以便电力可以从电线杆 $1$ 流向电线杆 $N$ 。没有电线可以长于某个实数 $M$ （ $\le 200000.0$ ）。

例如，下面左侧是暴风雨后 $9$ 根电线杆和 $3$ 根电线的地图。对于这个任务， $M = 2.0$ 。最佳的电线连接方案是连接电线杆 $4$ 和 $6$ ，以及电线杆 $6$ 和 $9$ 。

   暴风雨后                  最优重新连接
3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

总长度为 $1.414213562 + 1.414213562 = 2.828427124$ 。

分值：350

输入格式

第 $1$ 行：两个用空格分隔的整数： $N$ 和 $W$ 。

第 $2$ 行：一个实数： $M$ 。

第 $3…N+23\ldots N+2$ 行：每行包含两个用空格分隔的整数： $x_i$ 和 $y_i$ 。

第 $N+3…N+2+WN+3\ldots N+2+W$ 行：两个用空格分隔的整数： $P_i$ 和 $P_j$ 。

输出格式

第 1 行：单独一行上的一个整数。如果无法恢复连接，输出 -1。否则，输出一个整数，该整数是恢复电力所需的总最小成本的 $1000$ 倍。不要进行任何四舍五入；截断结果乘积。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

就像上面的图示一样。

如上所述。
（由 ChatGPT 4o 翻译）

C++实现

#include <bits/stdc++.h>
using namespace std;
int n, w;
double m, d[1001];
bool v[1001];
double a[1001][1001];
struct rec {
	double x, y;
} p[1001];
int main() {
	cin >> n >> w >> m;
	for (register int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
	for (register int i = 1; i <= n; ++i) 
		for (register int j = 1; j <= n; ++j) {
			a[i][j] = sqrt(pow(p[i].x - p[j].x, 2) + pow(p[i].y - p[j].y, 2));
			if (a[i][j] > m) a[i][j] = 1e18;
		}
	for (register int i = 1; i <= w; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[y][x] = a[x][y] = 0;
	}
	priority_queue<pair<double, int> > q;
	for (register int i = 1; i <= n; ++i) d[i] = 1e18;
	q.push(make_pair(0.0, 1));
	memset(v, 0, sizeof v);
	d[1] = 0;
	while (q.size()) {
		int x = q.top().second;
		q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (register int i = 1; i <= n; ++i) {
			double z = a[x][i];
			if (z == 1e18) continue;
			if (d[i] > d[x] + z) {
				d[i] = d[x] + z;
				q.push(make_pair(-d[i], i));
			}
		}
	}
	if (d[n] == 1e18) puts("-1");
	else printf("%.0lf", floor(d[n] * 1000));
}