{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "There are `N` network nodes, labelled `1` to `N`.\n",
    "\n",
    "Given `times`, a list of travel times as **directed** edges `times[i] = (u, v,\n",
    "w)`, where `u` is the source node, `v` is the target node, and `w` is the time\n",
    "it takes for a signal to travel from source to target.\n",
    "\n",
    "Now, we send a signal from a certain node `K`. How long will it take for all\n",
    "nodes to receive the signal? If it is impossible, return `-1`.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2\n",
    "    Output: 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Note:**\n",
    "\n",
    "  1. `N` will be in the range `[1, 100]`.\n",
    "  2. `K` will be in the range `[1, N]`.\n",
    "  3. The length of `times` will be in the range `[1, 6000]`.\n",
    "  4. All edges `times[i] = (u, v, w)` will have `1 <= u, v <= N` and `0 <= w <= 100`."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "network_delay_time (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function network_delay_time(times::Vector{Vector{Int}}, n::Int, k::Int)\n",
    "    graph = [Tuple{Int,Int}[] for _ in 1:n]\n",
    "    for (u, v, t) in times\n",
    "        push!(graph[u], (v, t))\n",
    "    end\n",
    "    pq = PriorityQueue{Int,Int}([(k, 0)])\n",
    "    res = Int[]\n",
    "    while !isempty(pq)\n",
    "        node, d = dequeue_pair!(pq)\n",
    "        for (neb, d1) in graph[node]\n",
    "            pq[neb] = min(get(pq, neb, typemax(Int)), d + d1)\n",
    "        end\n",
    "        push!(res, d)\n",
    "    end\n",
    "    return length(res) == n ? maximum(res) : -1\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}