diff options
Diffstat (limited to 'cheapest_flight_k_stop.c')
-rw-r--r-- | cheapest_flight_k_stop.c | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/cheapest_flight_k_stop.c b/cheapest_flight_k_stop.c new file mode 100644 index 0000000..2855eda --- /dev/null +++ b/cheapest_flight_k_stop.c @@ -0,0 +1,38 @@ +// 787. Cheapest Flights Within K Stops +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#define INF (INT_MAX >> 2) + +/* + * there are 'n' cities connected by some number of flights. you are given array + * 'flights' where 'flight[i] = [fromi, toi, pricei]' indicates that there is a + * flight from city 'fromi' to city 'toi' with cost 'pricei'. + * you are also given three integers 'src, dst, & k'. return the cheapest price + * from 'src' to 'dst' with at most 'k' stops. if there is no such route, -1 + */ + +int findCheapestPrice(int n, int **flights, int flightsSize, + int *flightsColSize, int src, int dst, int k) { + int *dist = malloc(n * sizeof(int)), *tmp = malloc(n * sizeof(int)); + for (int i = 0; i < n; i++) { + dist[i] = INF; + tmp[i] = INF; + } + dist[src] = 0; + tmp[src] = 0; + while (k >= 0) { + for (int i = 0; i < flightsSize; i++) { + int from = flights[i][0], to = flights[i][1], price = flights[i][2]; + if (tmp[to] > dist[from] + price) + tmp[to] = dist[from] + price; + } + memcpy(&dist[0], &tmp[0], n * sizeof(int)); + k--; + } + int ans = dist[dst]; + if (ans == INF) + return -1; + return ans; +} |