Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- int64_t INF = 1e10;
- struct Edge {
- int64_t from, to, weight;
- Edge(int64_t from, int64_t to, int64_t weight) : from(from), to(to), weight(weight) {};
- };
- class Graph {
- private:
- std::vector<std::vector<Edge>> edges;
- uint64_t vertex_count;
- public:
- Graph(uint64_t vertex_count) : vertex_count(vertex_count), edges(vertex_count) {};
- void AddEdge(int64_t from, int64_t to, int64_t weight) {
- edges[from].emplace_back(Edge(from, to, weight));
- }
- const std::vector<Edge>& GetEdges(int64_t from) const {
- return edges[from];
- }
- uint64_t Size() const {
- return vertex_count;
- }
- };
- std::vector<int64_t> GetDistancesMultiSourcesDijkstra(const Graph &graph, std::vector<int64_t> startPoints) {
- std::vector<int64_t> distances(graph.Size(), INF);
- std::vector<bool> used(graph.Size(), false);
- std::set<std::pair<int64_t, int64_t>> distance_processing;
- for (auto i : startPoints) {
- distances[i] = 0;
- distance_processing.insert(std::make_pair(distances[i], i ));
- }
- while (!distance_processing.empty()) {
- int64_t verticle_with_min_dist = distance_processing.begin()->second;
- distance_processing.erase(distance_processing.begin());
- if (!used[verticle_with_min_dist]) {
- used[verticle_with_min_dist] = true;
- for (const auto& edge : graph.GetEdges(verticle_with_min_dist)) {
- if (distances[verticle_with_min_dist] != INF) {
- if (distances[edge.to] > distances[verticle_with_min_dist] + edge.weight) {
- distance_processing.erase(std::make_pair(distances[edge.to], edge.to));
- distances[edge.to] = distances[verticle_with_min_dist] + edge.weight;
- distance_processing.insert(std::make_pair(distances[edge.to], edge.to));
- }
- }
- }
- }
- }
- return distances;
- }
- void Process(std::istream &is, std::ostream &os) {
- int64_t vertices, edges, fires;
- is >> vertices >> edges >> fires;
- std::vector<int64_t> fires_list(fires);
- for (auto &i : fires_list) {
- is >> i;
- --i;
- }
- Graph graph(vertices);
- while (edges--) {
- int64_t from, to, weight;
- is >> from >> to >> weight;
- graph.AddEdge(from - 1, to - 1, weight);
- graph.AddEdge(to - 1, from - 1, weight);
- }
- int64_t start_point, end_point;
- is >> start_point >> end_point;
- std::vector<int64_t> cavers_list = {start_point - 1};
- std::vector<int64_t> cavers_escape_times = GetDistancesMultiSourcesDijkstra(graph, cavers_list);
- int64_t cavers_out_time = cavers_escape_times[end_point - 1];
- std::vector<int64_t> fires_spread_times = GetDistancesMultiSourcesDijkstra(graph, fires_list);
- int64_t fire_out_time = fires_spread_times[end_point - 1];
- if (cavers_out_time < fire_out_time) {
- os << cavers_out_time << std::endl;
- } else {
- os << -1 << std::endl;
- }
- }
- int main() {
- Process(std::cin, std::cout);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement