【问题描述】飞机是远途旅行必不可少的工具，但是高昂的价格也令人颇费思量，因此人们往往宁愿用时间来换金钱而选择较慢的交通工具。不过，当航班线路变得丰富之后，人们也发现很多时候选择直达航班往往并非最省钱的路径，比如飞往美国选择从韩国转机就比直飞要便宜多了（虽然这样有坠机的危险）。这样一来，当采用曲线行进能达到省钱也省时间的目的时，坐飞机还是可以接受的。为了能够更好地解决路径的选择问题，我们模拟一下通过合适的算法来选出最优航空线路。参考http://flight.qunar.com/上的数据，自选至少10个城市和至少20条航线（不含中转），要求任意两城市间都可达（这并不意味着两个城市之间就一定有直飞航班，比如大陆到台湾），且至少有2条可选飞行路线。预先定义每条航线的最高定价，航线票价每季度都有折扣机会，但并非必须。每条线路每季度的折扣率由随机函数产生，范围是0.20～1.0（小数点后取两位）。本程序不考虑机场建设费和燃油附加费，只计算机票价格，将其作为路径上的权值处理，耗费矩阵存储结构自行选择。在真实的情形中，同一线路每天可能有许多航班，也可能每周只有一两趟航班，即便同一天的航班早晚价格也可能有所不同。为简便计，假定每条线路每天只有一趟航班，不考虑航空公司的差别。【基本要求】所有原始数据一律事先用文本文件保存，读入数据时从文件获取。航班价格可以用随机函数生成，但建议从网上直接复制真实数据。可输出所有城市名称以及每一城市所有可直飞到达的城市列表。可输出任一指定直飞线路（若没有则显示无直飞航班）四个季度的全票和折扣价格输入月份、起始城市和目的城市名称，程序能显示出直飞（如果有）以及最经济的中转路线选择方案。【输入输出】从文件中读取输入，具体格式自行决定。输出所有城市名以及每一城市所有可直飞到达的城市列表（按城市名拼音升序排列）：始发地 可直飞目的地北京 长春 广州 杭州 昆明 上海 首尔 武汉 香港……首尔 北京 上海 台北 香港……指定线路折扣和全价：输入：北京-台北输出：无直飞航班输入：北京-广州输出：季度 全票价格 折扣 折后价格（不计小数，四舍五入） 1 1240 6.5 806 2 1192 7.0 834 3 1475 4.6 679 4 1230 8.7 1070输入月份、起始城市和目的城市名称，输出直飞和最佳方案输入：5 北京-台北输出：无直飞航班，最佳线路：北京-香港，1503，香港-台北，791，合计2294输入：7 广州-首尔输出：直飞，2460，最佳线路：广州-上海，880，上海-首尔，773，合计1653输入：10 武汉-上海输出：直飞，278，最佳线路：武汉-上海，278，合计278……【实现提示】考虑到航线不太可能有单向情况，可将图简化成为无向图，但必须保证所有结点连通，所有线路（边）可以采用结构体形式保存其全价和随机产生的折扣，四个季度可以有不同的折扣和全价。可以考虑在折扣全部产生后直接使用Floyd算法。
