Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class iPair{
- int first, second;
- public iPair(int first, int second)
- {
- this.first = first;
- this.second = second;
- }
- }
- class Pair
- {
- int distance, node;
- public Pair(int distance, int node)
- {
- this.distance = distance;
- this.node = node;
- }
- }
- class Solution {
- public List<Integer> shortestPath(int n, int m, int edges[][]) {
- // Step-1 create an adjacency list
- ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
- for(int i=0;i<=n;i++)
- {
- adj.add(new ArrayList<iPair>());
- }
- for(int[] edge : edges)
- {
- 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 parent node array
- int[] distance = new int[n+1];
- int[] parent = new int[n+1];
- for(int i=0;i<=n;i++)
- {
- distance[i] = (int)1e9;
- parent[i] = i;
- }
- distance[1] = 0;
- // Step-3 Store the nodes into MIN-HEAP accoriding to node's weight
- pq.add(new Pair(0, 1));
- // Step-4 Traverse the nodes present in min-heap
- while(pq.size()!=0)
- {
- Pair pair = pq.poll();
- int currentNode = pair.node;
- int currentDist = pair.distance;
- for(iPair neighbour : adj.get(currentNode))
- {
- int adjNode = neighbour.first;
- int weight = neighbour.second;
- if(distance[adjNode] > (currentDist + weight))
- {
- distance[adjNode] = currentDist + weight;
- pq.add(new Pair(distance[adjNode], adjNode));
- parent[adjNode] = currentNode;
- }
- }
- }
- List<Integer> arr = new ArrayList<>();
- if(distance[n] == 1e9)
- {
- arr.add(-1);
- return arr;
- }
- int node = n;
- while(parent[node] != node)
- {
- arr.add(node);
- node = parent[node];
- }
- arr.add(1);
- arr.add(distance[n]);
- return arr;
- }
- }
RAW Paste Data
Copied
