Advertisement
IvetValcheva

01. Dora the Explorer

Oct 6th, 2022
833
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.21 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. import java.util.Scanner;
  5.  
  6. public class task1 {
  7.     public static void main(String[] args) {
  8.         Scanner scanner = new Scanner(System.in);
  9.  
  10.         int edgesCnt = Integer.parseInt(scanner.nextLine());
  11.         int nodes = edgesCnt * 2;
  12.  
  13.  
  14.         int[][] graph = new int[nodes][nodes];
  15.         List<int[]> edges = new ArrayList<>();
  16.  
  17.         for (int i = 0; i < edgesCnt; i++) {
  18.             int[] tokens = Arrays.stream(scanner.nextLine().split(", "))
  19.                     .mapToInt(Integer::parseInt)
  20.                     .toArray();
  21.  
  22.             graph[tokens[0]][tokens[1]] = tokens[2];
  23.             graph[tokens[1]][tokens[0]] = tokens[2];
  24.  
  25.             edges.add(new int[]{tokens[0], tokens[1]});
  26.             edges.add(new int[]{tokens[1], tokens[0]});
  27.         }
  28.  
  29.  
  30.  
  31.         int extraTime = Integer.parseInt(scanner.nextLine());
  32.  
  33.         int source = Integer.parseInt(scanner.nextLine());
  34.         int destination = Integer.parseInt(scanner.nextLine());
  35.  
  36.         int[] distances = new int[graph.length];
  37.  
  38.         Arrays.fill(distances, Integer.MAX_VALUE);
  39.  
  40.         int[] prev = new int[graph.length];
  41.  
  42.         Arrays.fill(prev, -1);
  43.  
  44.  
  45.         distances[source] = 0;
  46.  
  47.  
  48.         for (int i = 0; i < graph.length; i++) {
  49.             for (int[] edge : edges) {
  50.                 int from = edge[0];
  51.                 int to = edge[1];
  52.                 if (distances[from] != Integer.MAX_VALUE) {
  53.                     int newDistance = distances[from] + graph[from][to] + extraTime;
  54.                     if (newDistance < distances[to]) {
  55.                         distances[to] = newDistance;
  56.                         prev[to] = from;
  57.                     }
  58.                 }
  59.             }
  60.         }
  61.  
  62.  
  63.         List<Integer> path = new ArrayList<>();
  64.  
  65.         path.add(destination);
  66.  
  67.         int node = prev[destination];
  68.  
  69.         while (node != -1) {
  70.             path.add(node);
  71.             node = prev[node];
  72.         }
  73.  
  74.         System.out.println("Total time: " + (distances[destination] - extraTime));
  75.  
  76.         for (int i = path.size() - 1; i >= 0; i--) {
  77.             System.out.println(path.get(i));
  78.         }
  79.  
  80.  
  81.     }
  82. }
  83.  
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement