Advertisement
Guest User

Untitled

a guest
Nov 5th, 2019
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
ABAP 3.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. int64_t INF = 1e10;
  6.  
  7. struct Edge {
  8.     int64_t from, to, weight;
  9.     Edge(int64_t from, int64_t to, int64_t weight) : from(from), to(to), weight(weight) {};
  10. };
  11.  
  12. class Graph {
  13. private:
  14.     std::vector<std::vector<Edge>> edges;
  15.     uint64_t vertex_count;
  16. public:
  17.     Graph(uint64_t vertex_count) : vertex_count(vertex_count), edges(vertex_count) {};
  18.  
  19.     void AddEdge(int64_t from, int64_t to, int64_t weight) {
  20.         edges[from].emplace_back(Edge(from, to, weight));
  21.     }
  22.  
  23.     const std::vector<Edge>& GetEdges(int64_t from) const {
  24.         return edges[from];
  25.     }
  26.  
  27.     uint64_t Size() const {
  28.         return vertex_count;
  29.     }
  30. };
  31.  
  32.  
  33. std::vector<int64_t> GetDistancesMultiSourcesDijkstra(const Graph &graph, std::vector<int64_t> startPoints) {
  34.     std::vector<int64_t> distances(graph.Size(), INF);
  35.     std::vector<bool> used(graph.Size(), false);
  36.     std::set<std::pair<int64_t, int64_t>> distance_processing;
  37.    
  38.     for (auto i : startPoints) {
  39.         distances[i] = 0;
  40.         distance_processing.insert(std::make_pair(distances[i], i ));
  41.     }
  42.    
  43.     while (!distance_processing.empty()) {
  44.         int64_t verticle_with_min_dist = distance_processing.begin()->second;
  45.         distance_processing.erase(distance_processing.begin());
  46.         if (!used[verticle_with_min_dist]) {
  47.             used[verticle_with_min_dist] = true;
  48.             for (const auto& edge : graph.GetEdges(verticle_with_min_dist)) {
  49.                 if (distances[verticle_with_min_dist] != INF) {
  50.                     if (distances[edge.to] > distances[verticle_with_min_dist] + edge.weight) {
  51.                         distance_processing.erase(std::make_pair(distances[edge.to], edge.to));
  52.                         distances[edge.to] = distances[verticle_with_min_dist] + edge.weight;
  53.                         distance_processing.insert(std::make_pair(distances[edge.to], edge.to));
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.     }
  59.    
  60.     return distances;
  61. }
  62.  
  63. void Process(std::istream &is, std::ostream &os) {
  64.     int64_t vertices, edges, fires;
  65.     is >> vertices >> edges >> fires;
  66.    
  67.     std::vector<int64_t> fires_list(fires);
  68.    
  69.     for (auto &i : fires_list) {
  70.         is >> i;
  71.         --i;
  72.     }
  73.    
  74.     Graph graph(vertices);
  75.     while (edges--) {
  76.         int64_t from, to, weight;
  77.         is >> from >> to >> weight;
  78.        
  79.         graph.AddEdge(from - 1, to - 1, weight);
  80.         graph.AddEdge(to - 1, from - 1, weight);
  81.     }
  82.    
  83.     int64_t start_point, end_point;
  84.     is >> start_point >> end_point;
  85.    
  86.     std::vector<int64_t> cavers_list = {start_point - 1};
  87.     std::vector<int64_t> cavers_escape_times = GetDistancesMultiSourcesDijkstra(graph, cavers_list);
  88.     int64_t cavers_out_time = cavers_escape_times[end_point - 1];
  89.     std::vector<int64_t> fires_spread_times = GetDistancesMultiSourcesDijkstra(graph, fires_list);
  90.     int64_t fire_out_time = fires_spread_times[end_point - 1];
  91.    
  92.     if (cavers_out_time < fire_out_time) {
  93.         os << cavers_out_time << std::endl;
  94.     } else {
  95.         os << -1 << std::endl;
  96.     }
  97. }
  98.  
  99. int main() {
  100.    
  101.     Process(std::cin, std::cout);
  102.  
  103.     return 0;
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement