787. K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [fromi, toi, pricei] ,表示该航班都从城市 fromi 开始,以价格 pricei 抵达 toi。
现在给定所有的城市和航班,以及出发城市 src 和目的地 dst,你的任务是找到出一条最多经过 k 站中转的路线,使得从 src 到 dst 的 价格最便宜 ,并返回该价格。 如果不存在这样的路线,则输出 -1。
事例1:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如下:
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200,如图中红色所示。
事例1:
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500,如图中蓝色所示。
using System; // using System.Security.AccessControl; using Newtonsoft.Json; // JsonConvert // using Newtonsoft.Json.Linq; // JObject namespace ConsoleAppDemoOne { public static class ProgramOne { public static void Main(string[] args) { var nInput = Console.ReadLine(); var flightsInput = Console.ReadLine(); var srcInput = Console.ReadLine(); var dstInput = Console.ReadLine(); var kInput = Console.ReadLine(); var n = Convert.ToInt32(nInput); var scr = Convert.ToInt32(srcInput); var dst = Convert.ToInt32(dstInput); var k = Convert.ToInt32(kInput); Console.WriteLine(n.GetType()); // /*sing Newtonsoft.Json; // JsonConvert // using Newtonsoft.Json.Linq; // JObject*/ // var flights = (JObject)JsonConvert.DeserializeObject(flightsInput); // Console.WriteLine(flights); // Console.WriteLine(flights.GetType()); try { var flights = JsonConvert.DeserializeObject<int[][]>(flightsInput ?? string.Empty); Console.WriteLine(flights); if (flights == null) return; Console.WriteLine(flights.GetType()); var sl = new Solution(); Console.WriteLine(sl.FindCheapestPrice(n, flights, scr, dst, k)); // Console.ReadKey(); } catch (Exception ex) { Console.WriteLine(ex); } } } public class Solution { public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) { const int inf = 10000 * 101 + 1; // int[,] f = new int[k + 2, n]; var f = new int[k + 2, n]; for (var i = 0; i < k + 2; ++i) { for (var j = 0; j < n; ++j) { f[i, j] = inf; } } f[0, src] = 0; for (var t = 1; t <= k + 1; ++t) { foreach (var flight in flights) { int j = flight[0], i = flight[1], cost = flight[2]; f[t, i] = Math.Min(f[t, i], f[t - 1, j] + cost); } } var ans = inf; for (var t = 1; t <= k + 1; ++t) { ans = Math.Min(ans, f[t, dst]); } return ans == inf ? -1 : ans; } } }
try { var flights = JsonConvert.DeserializeObject<int[][]>(flightsInput ?? string.Empty); Console.WriteLine(flights); if (flights == null) return; Console.WriteLine(flights.GetType()); var sl = new Solution(); Console.WriteLine(sl.FindCheapestPrice(n, flights, scr, dst, k)); // Console.ReadKey(); } catch (Exception ex) { Console.WriteLine(ex); }
c#_转换这类"[[0,1,100],[1,2,100],[0,2,500]]"数组字符串为数组_Newtonsoft.Json