Проблемы кратчайшего пути Java - PullRequest
Новая
       2

Проблемы кратчайшего пути Java

0 голосов
/ 26 ноября 2018

Я пытаюсь решить проблему кратчайшего пути.Это старый вопрос Ватерлоо, и я тренируюсь в 2019 году. По сути, это «книга для приключенцев», есть N страниц (до 10000), каждая страница может привести к Ni страницам.Первый вход - N, затем есть N строк ввода, где первое число - это число ветвей на других страницах, за которыми следует страница, на которую оно ветвится.Если это 0, это конечная точка и других ветвей нет.Мы должны указать, все ли страницы достигнуты и указан кратчайший путь.Пример ввода и вывода: 

input:
3
2 2 3
0
1 1
output
Y
2

Мне удалось решить проблему, однако я продолжаю проваливать тесты с ограничением по времени.Как я могу сделать свой код более эффективным, чтобы пройти тесты времени?Вот мой рекурсивный метод, который я использую, чтобы избежать циклов и получить кратчайший путь. 

   public static void shortestPath(Page p, ArrayList<Page> list){
        ArrayList<Page> currentList = new ArrayList<>();
        for(Page pg : list){
            currentList.add(pg);
        }
        p.visited = true;
        if(p.paths.get(0) == 0){
            currentList.add(p);
            Paths temp = new Paths();
            temp.aPath = currentList;
            completedPaths.add(temp);
        }else{
            for(int i=0;i<p.paths.size();i++){
                if(!currentList.contains(pages.get(p.paths.get(i) - 1))){
                    if(!currentList.contains(p)){
                        currentList.add(p);
                    }
                    shortestPath(pages.get(p.paths.get(i) - 1), currentList);
                }
            }
        }
   }
...