Как найти кратчайший путь к 4 пунктам назначения в DAG? - PullRequest
0 голосов
/ 05 октября 2019

Я довольно новичок в программировании, и я вступил в Клуб программирования в своей школе, и я решаю некоторые вопросы из австралийского пакета CodeQuest 2018, и я озадачен одним вопросом, в частности проблемой 23: Доминирование в Disney:Вопрос в следующем: -

Ваша семья собирается в Disney World в Орландо, штат Флорида, в самое загруженное время года, поэтому вам предстоит спланировать наиболее эффективный способ совершить поездку на самых популярных аттракционах: ПиратыКарибского моря, Поезд Шахты Семи Гномов, Космическая Гора и Всплеск Горы. Ваша задача - найти самый быстрый способ навигации среди толп, припаркованных колясок и встречающихся персонажей.

На приведенной ниже карте показано расположение всех четырех аттракционов и пути, которые ведут к ним. Вам будет предоставлено количество времени, необходимое для прохождения каждого пути. Если между двумя или более путями существует связь, выберите путь, который начинается с наименьшего пути #. Например, если путь № 1> путь № 2> путь № 4> путь № 6 занимает столько же времени, что и путь № 7> путь № 6> путь № 4> путь № 2, вам следует выбрать первый вариант. Иногда может быть быстрее всего вернуться к поездке, на которой вы уже были!

Карта: https://imgur.com/a/2xuUrPW

Ввод программы: первая строка файла Prob23.in.txt будет содержатьположительное целое число T, обозначающее количество следующих тестовых случаев. Каждый тестовый пример будет иметь следующий вход: одну строку с семью натуральными числами, разделенными пробелами, что соответствует времени, которое потребуется для прохождения каждого из семи путей на карте выше. Время пути будет в порядке, начиная со времени пути № 1 и заканчивая путем № 7. Все времена пути будут больше 0.

Пример ввода:

3
5 10 7 6 2 4 12
15 8 20 7 20 5 10
4 810 6 6 8 10
Выход: 1 2 4 6
7 6 4 2
1 2 4 6

Вот некоторый стартовый код:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;

public class Problem23 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scan = new Scanner(new File("src/inputs/Prob23.in.txt"));
        int t = scan.nextInt();
        for(int i = 0; i < t; i++){
            int p1 = scan.nextInt();
            int p2 = scan.nextInt();
            int p3 = scan.nextInt();
            int p4 = scan.nextInt();
            int p5 = scan.nextInt();
            int p6 = scan.nextInt();
            int p7 = scan.nextInt();
            DominatingDisney(p1,p2,p3,p4,p5,p6,p7);
        }
    }
    public static void DominatingDisney(int p1, int p2, int p3, int p4, int p5, int p6, int p7){
    }
}

Iискал что-то подобное в Интернете и столкнулся с DAG, которые, как мне кажется, являются диаграммой, приведенной выше. Однако я понятия не имею, что это такое и как они работают, я не мог найти никаких ресурсов, дающих мне четкое объяснение. Мне очень жаль, если этот вопрос раздражает. Спасибо, если вы окажете какую-либо помощь. Снова извините и спасибо!

Вещи, которые я пробовал:
Переход к каждой станции по одной. Но это не самый быстрый маршрут, а самый быстрый, если вы едете на станции по часовой стрелке.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...