47. Cheapest Flight within K Stops Code

Medium

Problem Statement

Given n cities and flight prices, find the cheapest price from src to dst with up to k stops. Return -1 if no such route exists.

Examples

1Example 1

Input:

{
  "n": 4,
  "flights": [
    [
      0,
      1,
      100
    ],
    [
      1,
      2,
      100
    ],
    [
      2,
      0,
      100
    ],
    [
      1,
      3,
      600
    ],
    [
      2,
      3,
      200
    ]
  ],
  "src": 0,
  "dst": 3,
  "k": 1
}

Output:

700

2Example 2

Input:

{
  "n": 3,
  "flights": [
    [
      0,
      1,
      100
    ],
    [
      1,
      2,
      100
    ],
    [
      0,
      2,
      500
    ]
  ],
  "src": 0,
  "dst": 2,
  "k": 1
}

Output:

200

3Example 3

Input:

{
  "n": 3,
  "flights": [
    [
      0,
      1,
      100
    ],
    [
      1,
      2,
      100
    ],
    [
      0,
      2,
      500
    ]
  ],
  "src": 0,
  "dst": 2,
  "k": 0
}

Output:

500