Number of Ways to Arrive at Destination

shriyanshi24jindal

Mar 30th, 2026

135

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 15.70 KB | None | 0 0

copy raw download clone embed print report

class Pair
{
int node;
long dist;
Pair(int node, long dist)
{
this.node = node;
this.dist = dist;
}
}
class iPair
{
int vertex;
int weight;
iPair(int vertex, int weight)
{
this.vertex = vertex;
this.weight = weight;
}
}
class Solution {
/**
Build adjacency list from the edge list.
Use Dijkstra to find shortest distances from node 0 to all nodes
Maintain a ways[] array:
ways[u] = number of shortest paths to node u.
If a new shorter path is found, update distance and ways.
If an equal distance is found, add ways.
Return ways[V-1] → number of shortest paths to last node.
*/
public int countPaths(int V, int[][] roads) {
int MOD = 1_000_000_007;
// Step-1 Create an adjacency list
ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<iPair>());
}
for(int[] edge : roads)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new iPair(v, w));
adj.get(v).add(new iPair(u, w));
}
// Step-2 Create a distance array and count ways array
long[] distance = new long[V];
int[] ways = new int[V];
Arrays.fill(distance, Long.MAX_VALUE);
// starting node is 0 so distance will be 0 and no of ways to reach from node 0-> node 0 is 1
distance[0] = 0;
ways[0] = 1;
// Step-3 Define Priority queue to store the nodes according to shortest distance
PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Long.compare(x.dist, y.dist));
pq.add(new Pair(0, 0));
while(!pq.isEmpty())
{
Pair pair = pq.poll();
int currentNode = pair.node;
long currentDist = pair.dist;
// stale entry
if(currentDist > distance[currentNode])
continue;
for(iPair adjNode : adj.get(currentNode))
{
int vertex = adjNode.vertex;
int weight = adjNode.weight;
if(distance[vertex] > currentDist + weight)
{
distance[vertex] = currentDist + weight;
pq.offer(new Pair(vertex, distance[vertex]));
ways[vertex] = ways[currentNode];
}
else if(distance[vertex] == currentDist + weight)
{
ways[vertex] = (ways[vertex]+ways[currentNode]) % MOD;
}
}
}
return ways[V-1];
}
}

RAW Paste Data Copied

class Pair
{
    int node;
    long dist;
    Pair(int node, long dist)
    {
        this.node = node;
        this.dist = dist;
    }
}
class iPair
{
    int vertex;
    int weight;
    iPair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
    Build adjacency list from the edge list.
    Use Dijkstra to find shortest distances from node 0 to all nodes
    Maintain a ways[] array:
        ways[u] = number of shortest paths to node u.
        If a new shorter path is found, update distance and ways.
        If an equal distance is found, add ways.
    Return ways[V-1] → number of shortest paths to last node. 
    */
    public int countPaths(int V, int[][] roads) {
        int MOD = 1_000_000_007;

// Step-1 Create an adjacency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<iPair>());
        }

for(int[] edge : roads)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];

adj.get(u).add(new iPair(v, w));
            adj.get(v).add(new iPair(u, w));
        }

// Step-2 Create a distance array and count ways array
        long[] distance = new long[V];
        int[] ways = new int[V];
        Arrays.fill(distance, Long.MAX_VALUE);
        // starting node is 0 so distance will be 0 and no of ways to reach from node 0-> node 0 is 1
        distance[0] = 0;
        ways[0] = 1;

// Step-3 Define Priority queue to store the nodes according to shortest distance
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Long.compare(x.dist, y.dist));
        pq.add(new Pair(0, 0));

while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            long currentDist = pair.dist;

// stale entry
            if(currentDist > distance[currentNode]) 
                continue;

for(iPair adjNode : adj.get(currentNode))
            {
                int vertex = adjNode.vertex;
                int weight = adjNode.weight;

if(distance[vertex] > currentDist + weight)
                {
                    distance[vertex] = currentDist + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                    ways[vertex] = ways[currentNode];
                }
                else if(distance[vertex] == currentDist + weight) 
                {
                    ways[vertex] = (ways[vertex]+ways[currentNode]) % MOD;
                }
            }
        }
        return ways[V-1];
    }
}