1003. Emergency (25)-白红宇

1003. Emergency (25)

阅读量：797 次

发布时间：2023-03-23

本文共 3062 字，大约阅读时间需要 10 分钟。

为了解决这个问题，我们需要找到从我所在城市到目标城市的最短路径，并且在这条路径上尽可能多地聚集消火员，以最大限度地扑灭火灾。这个问题可以通过扩展Dijkstra算法来解决，其中不仅追求路径长度的最短，还考虑路径上的消火员数量之和。

分析与解题步骤

理解问题：我们需要找到从起点到终点的最短路径，并且在这条路径上，消火员的数量之和尽可能大。这里假设消火员数量是路径上的各个城市的消火员数量之和，或者是路径上的每个节点的消火员数量的最大值。

选择算法：Dijkstra算法适用于寻找从一个点到另一个点的最短路径。我们可以扩展这个算法，使其不仅考虑路径长度，还考虑其他属性，比如消火员数量。

扩展Dijkstra算法：在Dijkstra算法中，每次选取距离源点最近的节点进行处理。在我们的问题中，每次处理节点时，不仅更新距离，还要更新消火员数量。如果两条路径长度相同，选择消火员数量更多的路径。

图的表示：图可以是无向的，因为消火员可以从任何方向赶到目标城市。需要确保图的边是双向的，或者在有向图中正确处理方向。

初始化与数据结构：使用一个优先队列来处理节点，按照距离排序。当距离相同时，按照消火员数量排序。每个节点需要记录当前的最短距离、消火员数量和道路数量。

实现步骤：

初始化所有节点的距离为无穷大，消火员数量为0，道路数量为0。

起点的距离设为0，消火员数量设为初始值。

使用优先队列处理节点，更新其邻接节点的距离、消火员数量和道路数量。

在更新时，如果路径更短，完全替换旧的路径；如果路径长度相同，但消火员数量更多，则更新消火员数量。

测试与验证：构造不同的测试用例，验证算法是否正确处理不同的情况，包括路径长度相同但消火员数量不同的情况。

代码优化与实现

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
using namespace std;
struct City {
    int roadNum; // 边的数量
    int emergencyNum; // 消火员数量
    int distance; // 距离
};
vector
        
          cities; vector
         
          
           > map; vector
           
             visit; vector
            
              team; void digistra(int start, int end) { int n = cities.size(); for (int i = 0; i < n; ++i) { cities[i].distance = INF; cities[i].emergencyNum = 0; cities[i].roadNum = 0; } cities[start].distance = 0; cities[start].emergencyNum = team[start]; cities[start].roadNum = 1; priority_queue
             
              
               > pq; pq.push({0, start}); visit[start] = true; while (!pq.empty()) { int d, u = get<1>(pq.top()); pq.pop(); if (u == end) break; if (d > cities[u].distance) continue; for (int v = 0; v < n; ++v) { if (visit[v] || map[u][v] == INF) continue; if (cities[v].distance > cities[u].distance + map[u][v]) { cities[v].distance = cities[u].distance + map[u][v]; cities[v].emergencyNum = cities[u].emergencyNum + team[v]; cities[v].roadNum = cities[u].roadNum; visit[v] = true; pq.push({cities[v].distance, v}); } else if (cities[v].distance == cities[u].distance + map[u][v]) { if (cities[v].emergencyNum < cities[u].emergencyNum + team[v]) { cities[v].emergencyNum = cities[u].emergencyNum + team[v]; cities[v].roadNum = cities[u].roadNum; visit[v] = true; pq.push({cities[v].distance, v}); } } } } } int main() { int cityNum; while (true) { scanf("%d", &cityNum); if (cityNum == -1) break; int roadNum, startPoint, endPoint; scanf("%d %d %d", &roadNum, &startPoint, &endPoint); team.resize(cityNum); visit.resize(cityNum, false); map.resize(cityNum); for (int i = 0; i < cityNum; ++i) { map[i].resize(cityNum, INF); } for (int i = 0; i < cityNum; ++i) { scanf("%d", &team[i]); } for (int i = 0; i < roadNum; ++i) { int myStart, myEnd, myLength; scanf("%d %d %d", &myStart, &myEnd, &myLength); if (myStart != myEnd) { if (map[myStart][myEnd] > myLength) { map[myStart][myEnd] = myLength; map[myEnd][myStart] = myLength; } } } digistra(startPoint, endPoint); printf("%d %d\n", cities[endPoint].roadNum, cities[endPoint].emergencyNum); } return 0; }

解释

City结构：每个城市包含道路数量、消火员数量和到起点的距离。

digistra函数：扩展的Dijkstra算法，不仅更新距离，还更新消火员数量。如果路径长度相同，选择消火员数量更多的路径。

优先队列：按距离和消火员数量排序，确保每次处理最优路径。

图的处理：允许多个方向的边，确保消火员可以从任何方向赶到目标城市。

通过这种方法，我们可以找到最短路径，并在路径上聚集最多的消火员，从而有效扑灭火灾。

转载地址：http://flqfk.baihongyu.com/

你可能感兴趣的文章