CCF CSP 第30次（2023.05）（4_电力网络_C++）

时间限制： 1.0 秒
空间限制： 512 MiB
原题链接

解题思路：

思路一：

1、解题步骤拆分：
① 数据输入：

• 第一行输入三个整数 N M K。
• 接下来 N 行每行输入 K 个整数 (代表每个城市的K个候选地址的变电站造价，使用 vecor 来存储)。
• 接下来 M 行每行输入 K²+2个整数(前两个整数表示该输电线路两端的城镇，第三个整数开始是大小为 K×K 的矩阵T，T[i][j] 代表 i 和 j 之间输电线路的价格）。

② 数据处理：

• 在输入一行 两个城市之间的输入输电线路价格时，就可以对两城市之间的最小费用进行计算。在两个城市各挑选一座变电站，搭成一条输电线计算其价格最小的情况。
• 每处理两个城市，将最小的造价进行累加。

③ 数据输出：电网的总造价。

代码实现

代码实现（思路一）：

#include<iostream>
#include<vector>
using namespace std;int main(int argc, char const *argv[])
{int N, M, K;cin >> N >> M >> K;  // 读取 N, M, K// 创建一个二维数组来存储每个城市的K个候选变电站的价格vector<vector<int>> Substation_price(N, vector<int>(K));// i代表城市 j代表该城市的第j个变电站for (int i = 0; i < N; i++) {for (int j = 0; j < K; j++) {cin >> Substation_price[i][j];  // 输入每个城市的变电站造价}}int all_min_sum = 0;  // 用于累加所有输电线路的最小总费用// 遍历所有的输电线路for (int row = 0; row < M; row++) {int p1, p2;cin >> p1 >> p2;  // 读取输电线路的两个城市int min_sum = INT_MAX;  // 初始化最小费用为一个非常大的数int line_Price;  // 存储每对变电站之间的输电线路的价格// 遍历所有可能的变电站对 (i, j)for (int i = 0; i < K; i++) {for (int j = 0; j < K; j++) {cin >> line_Price;  // 输入城市 p1 到城市 p2 之间的输电线路价格// 计算该线路总费用：变电站的造价 + 输电线路的费用int value = line_Price + Substation_price[p1][i] + Substation_price[p2][j];// 如果该总费用更小，则更新最小费用if (value < min_sum) {min_sum = value;}}}all_min_sum += min_sum;  // 将最小费用累加到总费用中}cout << all_min_sum;  // 输出最终的最小总费用return 0;
}

欢迎大家和我沟通交流(✿◠‿◠)