제출 #974747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974747		Nalrimet	007 (CEOI14_007)	C++17	0 / 100	333 ms	27560 KiB

007

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

std::vector<std::vector<int>> init_graph(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> graph(n + 1);
    for (auto& edge : edges) {
        graph[edge.first].push_back(edge.second);
        graph[edge.second].push_back(edge.first);
    }
    return graph;
}

std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<int> distances(graph.size(), -1);
    std::queue<int> q;
    q.push(start);
    distances[start] = 0;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int neighbor : graph[current]) {
            if (distances[neighbor] == -1) {
                distances[neighbor] = distances[current] + 1;
                q.push(neighbor);
            }
        }
    }
    return distances;
}

int main() {
    int N, M, s, d, a, b;
    std::cin >> N >> M;
    std::cin >> s >> d >> a >> b;

    std::vector<std::pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> edges[i].first >> edges[i].second;
    }

    auto graph = init_graph(N, edges);
    auto distances_s = bfs(graph, s);
    auto distances_d = bfs(graph, d);

    int a1 = distances_s[a], a2 = distances_s[b];
    int b1 = distances_d[a], b2 = distances_d[b];
    int w1 = b1 - a1, w2 = b2 - a2;

    // Стратегия для определения максимального времени ожидания
    int max_wait_time = -1;
    if ((w1 < 0 && w2 < 0) || (a1 == -1 && a2 == -1)) {
        max_wait_time = -1;  // 007 не может вообще победить, если она не достигает серверов
    } else {
        if (w1 == w2) {
            max_wait_time = std::max(0, w1);  // Максимальное время ожидания равно минимальному w
        } else {
            max_wait_time = std::max(0, std::min(w1, w2));  // Берем минимальное значение w
        }
    }

    std::cout << max_wait_time << std::endl;
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70