network-delay-time

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are given a network of <code>n</code> nodes, labeled from <code>1</code> to <code>n</code>. You are also given <code>times</code>, a list of travel times as directed edges <code>times[i] = (ui, vi, wi)</code>, where <code>ui</code> is the source node, <code>vi</code> is the target node, and <code>wi</code> is the time it takes for a signal to travel from source to target.

We will send a signal from a given node <code>k</code>. Return the minimum time it takes for all the <code>n</code> nodes to receive the signal. If it is impossible for all the <code>n</code> nodes to receive the signal, return <code>-1</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png" style="width: 217px; height: 239px;" />
<pre>
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
</pre>

Example 2:

<pre>
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
</pre>

Example 3:

<pre>
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= times.length &lt;= 6000</code></li>
	<li><code>times[i].length == 3</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li><code>ui != vi</code></li>
	<li><code>0 &lt;= wi &lt;= 100</code></li>
	<li>All the pairs <code>(ui, vi)</code> are unique. (i.e., no multiple edges.)</li>
</ul>