C++ 图邻接表或矩阵

Question

发电厂 该地区的几座发电厂昨晚发生爆炸。 我们还不知道为什么；我们的工程团队仍在努力解决这个问题。 为了应对紧急情况，我们有几个移动电站。
我们需要弄清楚哪些城市停电了，这样我们才能把他们送到那里。

还好我们还有原来的电网规划 并且已经从中移除了炸毁的发电厂。

更新后的计划现在显示剩余的发电厂， 它们的供电范围以及它们与电网的连接。

这应该足以让你弄清楚哪些城市没有得到电力。

您将获得电网和电厂的信息（电厂编号和供电范围）。
你应该找出哪些城市停电了。 发电厂可以为自己和相连的城市供电，但范围有限

输入： 第 1 行：地点之间的一组连接，地点是发电站 (P) 或城市 (C) 第 2 行：一组发电站和范围 所需输出：一组字符串。每个字符串都是一个被涂黑的城市的名称。

例子： 输入 1：（P6、C2）（C1、C2）（C1、C3）（C3、P5）（C2、C7）（C6、P6） 输入 2：（P6，1），（P5，1） 城市名称始终以 C 开头，电厂名称始终以 P 开头。

P6 - C2 - C1 - C3 - P5 |
C6 C7

输出：(C1)(C7)

我只有图的理论知识，正在寻找这个问题的解决方案

我从下面的起始代码开始-

`int main() {
  vector<pair<string,string>> powerStations { make_pair("P6", "C2"), 
                                              make_pair("C1", "C2"),  
                                              make_pair("C1", "C3"),  
                                              make_pair("C3", "P5"),  
                                              make_pair("C2", "C7"), 
                                              make_pair("C6", "P6")};

  vector<pair<string, unsigned int>> strength {make_pair("P6", 1), make_pair("P5", 1)}; 

  return 0;
}`

Answer 1

你需要找到从发电厂范围内仍在运行的发电厂可以到达哪些城市。

所以你需要找到从每个发电厂到每个城市的最短路径距离。任何距离任何发电厂太远的城市都会被停电。

- LOOP P over power plants
   - Apply Dijkstra algorithm to get distance from P to every city
   - LOOP C over cities
       - IF C is within range of P
             - MARK C as OK
- LOOP C over cities
     IF C is NOT marked OK
          - OUTPUT C as blacked out.