0

Решаю задачу из Яндекс.Контеста. Проходит 15 тестов, на 16 пишет, что неверный ответ. Наверняка упускаю какое-то граничное условие, но уже перепробовал всё, что пришло в голову: в случае, когда есть 2 равных по длине пути от города А до города Б, подсчитываются дороги кратчайшего из них (пример такого варианта оставлю внизу). Несуществующие выдают -1. Подскажите, пожалуйста, в чём может быть загвоздка?

G. Интересное путешествие

Ограничение времени 1 секунда

Ограничение памяти 64Mb

Ввод стандартный ввод или input.txt

Вывод стандартный вывод или output.txt

Не секрет, что некоторые программисты очень любят путешествовать. Хорошо всем известный программист Петя тоже очень любит путешествовать, посещать музеи и осматривать достопримечательности других городов.

Для перемещений между из города в город он предпочитает использовать машину. При этом он заправляется только на станциях в городах, но не на станциях по пути. Поэтому он очень аккуратно выбирает маршруты, чтобы машина не заглохла в дороге. А ещё Петя очень важный член команды, поэтому он не может себе позволить путешествовать слишком долго. Он решил написать программу, которая поможет ему с выбором очередного путешествия. Но так как сейчас у него слишком много других задач, он попросил вас помочь ему.

Расстояние между двумя городами считается как сумма модулей разности по каждой из координат. Дороги есть между всеми парами городов.

Формат ввода

В первой строке входных данных записано количество городов n (2≤n≤1000). В следующих n строках даны два целых числа: координаты каждого города, не превосходящие по модулю миллиарда. Все города пронумерованы числами от 1 до n в порядке записи во входных данных.

В следующей строке записано целое положительное число k, не превосходящее двух миллиардов, — максимальное расстояние между городами, которое Петя может преодолеть без дозаправки машины.

В последней строке записаны два различных числа — номер города, откуда едет Петя, и номер города, куда он едет.

Формат вывода

Если существуют пути, удовлетворяющие описанным выше условиям, то выведите минимальное количество дорог, которое нужно проехать, чтобы попасть из начальной точки маршрута в конечную. Если пути не существует, выведите -1.

введите сюда описание изображения

import java.io.*;

class Main {
static final String input = "input.txt";
static final String output = "output.txt";
static BufferedReader br;
static BufferedWriter bw;

static int maxDistance;

public static void main(String[] args) throws IOException {
    br = new BufferedReader(new FileReader(input));
    bw = new BufferedWriter(new FileWriter(output));

    int citiesN = Integer.parseInt(br.readLine());
    int[] x = new int[citiesN];
    int[] y = new int[citiesN];

    for (int i = 0; i < citiesN; i++) {
        String line = br.readLine();
        String[] tokens = line.split(" ");
        x[i] = Integer.parseInt(tokens[0]);
        y[i] = Integer.parseInt(tokens[1]);

    }

    maxDistance = Integer.parseInt(br.readLine());
    String line = br.readLine();
    String[] tokens = line.split(" ");
    int startCity = Integer.parseInt(tokens[0]) - 1;
    int endCity = Integer.parseInt(tokens[1]) - 1;


    swap(x, y, 0, startCity);
    swap(x, y, x.length - 1, endCity);

    int[][] matrix = new int[citiesN][citiesN];
    for (int i = 0; i < citiesN; i++) {
        for (int j = 0; j < citiesN; j++) {

            int distance = Math.abs(x[j] - x[i]) + Math.abs(y[j] - y[i]);
            if (distance <= maxDistance) {
                matrix[i][j] = distance;
            } else {
                matrix[i][j] = 0;
            }
        }
    }
    int minWays = dijkstra(matrix);
    bw.write(String.valueOf(minWays));
    br.close();
    bw.close();
}

private static void swap(int[] x, int[] y, int source, int startCity) {
    int temp = x[source];
    x[source] = x[startCity];
    x[startCity] = temp;

    temp = y[source];
    y[source] = y[startCity];
    y[startCity] = temp;
}

public static int dijkstra(int[][] adjacencyMatrix) {
    int v = adjacencyMatrix.length;

    boolean[] visited = new boolean[v];
    int[] distance = new int[v];

    distance[0] = 0;
    for (int i = 1; i < v; i++) {
        distance[i] = Integer.MAX_VALUE;
    }
    int count = 1;
    int resultCount = 0;

    for (int i = 0; i < v - 1; i++) {
        // Find Vertex with Min distance
        int minVertex = findMinVertex(distance, visited);
        visited[minVertex] = true;
        // Explore neighbours
        for (int j = 0; j < v; j++) {
            if (adjacencyMatrix[minVertex][j] != 0 && !visited[j] && distance[minVertex] != Integer.MAX_VALUE) {
                int newDist = distance[minVertex] + adjacencyMatrix[minVertex][j];
                if (newDist < distance[j]) {
                    distance[j] = newDist;
                    if (j == v - 1) {
                        resultCount = count;
                        count = 0;
                    }
                }

            }

        }
        count++;

    }
    if (resultCount == 0) {
        return -1;
    } else return resultCount;
}

private static int findMinVertex(int[] distance, boolean[] visited) {
    int minVertex = -1;
    for (int i = 0; i < distance.length; i++) {
        if (!visited[i] && (minVertex == -1 || distance[i] < distance[minVertex])) {
            if (minVertex == -1)
                minVertex = i;
            else
                if (distance.length-1-minVertex<distance.length-1-i)
                    minVertex = i;

        }
    }
    return minVertex;
}

}

Пример с 2 одинаковыми путями:

5
0 0
0 2
3 3
3 2
3 1
5
1 3
3
  • Найден ли ответ или решение? Я наткнулся на такую же задачу, решил ее через BFS. Также на 15м тесте вылетает неправильный ответ. Тест не виден. 2 июл 2022 в 19:29
  • Кто-нибудь решил? Я сделал через BFS, вылетает на 21-м тесте с out of time.
    – dondublon
    5 сен 2022 в 15:22
  • Здесь какое-то сложное решение. Какие-то матрицы... Мне хватило массива для учета посещенных вершин и очереди для последовательного обхода. Ну то есть BFS, да 5 дек 2022 в 1:22

2 ответа 2

1

Если вам нужно найти количество дорог, то зачем здесь distance?

  if (distance <= maxDistance) {
            matrix[i][j] = distance;

Чтобы в Дейкстре учитывались перегоны, а не их протяжённость, достаточно

  matrix[i][j] = 1;

Кроме того, Дейкстра избыточен, хватит BFS (поиска в ширину)

2
  • Я поначалу решил, что нужно учитывать и расстояние до конечного города: может оказаться так, что одна трасса в 500 км, а при этом пятью объездными дорожками можно доехать за 100 км. С "matrix[i][j] = 1" ситуация аналогичная - падает на том же тесте(
    – Alox1d
    1 июн 2021 в 8:47
  • Ещё у вас в матрице получается единица, когда i=j, т.е. петля в графе. В дальнейшей обработке это учитывается?
    – MBo
    1 июн 2021 в 8:55
1

У меня таже проблема была с вылетом за пределы значений int при расчёте расстояний.

Надо испоьзовать long, когда расстояния считаешь.

1
  • Подтверждаю. У меня так было, пока этот ответ не увидел)) Причем, в какой-то момент решения я немного задумывался над этим, но почему-то ошибся и посчитал, что int-а хватит. 5 дек 2022 в 1:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.