minimum time to travel between stations

Question

I have implemented a Java program that aims to find the minimum time required to reach each station based on the given bus schedules using Breadth-First Search (BFS). However, the program consistently produces -1 as the output for all stations. I have carefully reviewed the code and I am unable to identify the cause of the issue. I would appreciate any insights or suggestions on why the program is not providing the expected results. Thank you in advance for your help. The input to the program consists of the following parts:

The first line contains two space-separated integers: N and M. N represents the total number of stations, and M represents the number of buses.

The next M lines describe the schedule of each bus. Each line starts with an integer, t, which represents the number of stations visited by that bus. Following t, there are t integers indicating the sequence of stations visited by the bus.

The output of the program is a single line containing N-1 space-separated integers. Each integer represents the minimum time required to reach a particular station (except the first station) from the starting station. If a station is not reachable based on the given bus schedules, the corresponding output will be -1.

In the provided sample input, we have 8 stations and 4 buses. The schedule of each bus is as follows:

Bus 1: Visits stations 5 and 4. Bus 2: Visits stations 6, 1, and 2. Bus 3: Visits stations 4, 2, 1, and 3. Bus 4: Visits stations 7 and 8. Based on these schedules, the program calculates the minimum time required to reach each station. The sample output is "2 3 4 6 3 -1 -1", which means it takes 2 minutes to reach station 2, 3 minutes to reach station 3, 4 minutes to reach station 4, 6 minutes to reach station 6, 3 minutes to reach station 7, and stations 8 and beyond are not reachable (-1).

`import java.util.*;

public class Main {
public static void main(String[] args) {
    // Step 1: Parse the input values
   

    // Step 2: Perform BFS to find the minimum time to reach each station
    int[] minTime = new int[N];
    Arrays.fill(minTime, -1); // Initialize all stations as unreachable
    minTime[0] = 0; // First station is reachable with 0 time

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0); // Start BFS from the first station

    while (!queue.isEmpty()) {
        int station = queue.poll();

        for (List<Integer> schedule : buses) {
            int time = minTime[station] + 1;

            for (int i = 0; i < schedule.size(); i++) {
                int nextStation = schedule.get(i);

                if (nextStation == station) {
                    // If the bus visits the current station, update the time to reach next station
                    i++; // Skip the current station
                    if (i < schedule.size()) {
                        nextStation = schedule.get(i);
                        if (minTime[nextStation] == -1 || time < minTime[nextStation]) {
                            minTime[nextStation] = time;
                            queue.offer(nextStation);
                        }
                    }
                    break;
                }
            }
        }
    }
    // Step 3: Print the minimum time to reach each station (except the first station)
    
}
}

`

what modification can I do to get the expected output

input is 8 4 2 5 4 3 6 1 2 4 4 2 1 3 2 7 8 output of this code is -1 -1 -1 -1 -1 -1 -1 the expected output is 2 3 4 6 3 -1 -1

Answer 1

I also tried djiskrat algorithm but same problem

  import java.util.*;

  public class Main {
    public static void main(String[] args) {
        // Step 1: Read the input values
     

        // Step 2: Initialize the minTime array
        int[] minTime = new int[N];
        Arrays.fill(minTime, -1);
        minTime[0] = 0;

        // Step 3: Use Dijkstra's algorithm to find the minimum time
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int station = node.station;
            int time = node.time;

            if (time > minTime[station]) {
                continue; // Skip if we have found a shorter time to reach this 
                                       station
            }

            for (List<Integer> schedule : buses) {
                for (int i = 0; i < schedule.size(); i++) {
                    if (schedule.get(i) == station) {
                        int travelTime = 1; // Time taken to travel to the next 
                                        station

                        int nextIndex = (i + 1) % schedule.size();
                        int nextStation = schedule.get(nextIndex);

                        int nextTime = time + travelTime;
                        if (minTime[nextStation] == -1 || nextTime < 
                           minTime[nextStation]) {
                            minTime[nextStation] = nextTime;
                            pq.offer(new Node(nextStation, nextTime));
                        }
                    }
                }
            }
        }

        // Step 4: Print the minimum time to reach each station
        
    }

    static class Node implements Comparable<Node> {
        int station;
        int time;

        public Node(int station, int time) {
            this.station = station;
            this.time = time;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(time, other.time);
        }
    }
}