[Ruby] Dijkstra + sorting by distance and iterating nodes
\nruby\ndef dijkstra(n, edge_list, init)\n  verts = *0...n\n  dist = Array.new(n, Float::INFINITY)\n  dist[init] = 0\n  prev = Array.new(n, nil)\n  adj = Hash.n
\n```ruby\ndef dijkstra(n, edge_list, init)\n  verts = *0...n\n  dist = Array.new(n, Float::INFINITY)\n  dist[init] = 0\n  prev = Array.new(n, nil)\n  adj = Hash.new { |adj, v| adj[v] = [] }\n  edge_list.each do |u, v, w|\n    adj[u] << [v, w]\n    adj[v] << [u, w]\n  end\n  pq = [[0, init]] # priority queue\n  visited = Set.new\n\n  while pq.any?\n    dist_v, v = pq.shift\n    next if dist[v] < dist_v\n    visited.add(v)\n    adj[v].each do |u, w|\n      next if visited.include?(u)\n      alt = dist[v] + w\n      if alt < dist[u]\n        idx = pq.bsearch_index { |d, _| alt <= d } || pq.size\n        pq.insert(idx, [alt, u])\n        dist[u] = alt\n        prev[u] = v\n      end\n    end\n  end\n\n  # in addition to distances, return adjacents nodes\n  return dist, adj\nend\n\nMOD = 10**9 + 7\ndef count_restricted_paths(n, edges)\n  edge_list = edges.map { |u, v, w| [u - 1, v - 1, w] }\n  dist, adj = dijkstra(n, edge_list, n - 1)\n  \n  count_paths = Array.new(n, 0)\n  count_paths[n - 1] = 1\n\n  (0...n).zip(dist).sort_by(&:last).each.each do |u, _|\n    for v, _ in adj[u]\n      if dist[u] > dist[v]\n        count_paths[u] += count_paths[v]\n        count_paths[u] %= MOD\n      end\n    end\n    break if u == 0\n  end\n\n  count_paths[0]\nend\n```
['Ruby']