地铁换乘-取最佳路线最低票价
package com;import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Set;////为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。////线1//苹果园//....//四惠东////线2//西直门//车公庄//....//建国门////线4//....////其中第一行数据为地铁线名，接下来是该线的站名。//当遇到空行时，本线路站名结束。////下一行开始又是一条新线....直到数据结束。//////如果多条线拥有同一个站名，表明：这些线间可以在该站换车。////为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：////1. 每条线路可以单独购票，票价不等。//2. 允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。////单线票价和联合票价如 price.txt 所示。////线1 180//.....//线13 114//线1,线2 350//线1,线10 390//.....//////每行数据表示一种票价//线名与票价间用空格分开。如果是联票，线名间用逗号分开。//联票只能包含两条可换乘的线路。////现在的问题是：根据这些已知的数据，计算从A站到B站最小花费和可行的换乘方案。////比如，对于本题目给出的示例数据////如果用户输入：//五棵松,奥体中心////程序应该输出：//-(线1,线10)-线8 = 565////如果用户输入：//五棵松,霍营////程序应该输出：//-线1-(线4,线13) = 440////可以看出，用户输入的数据是：起始站，终到站，用逗号分开。//程序输出了购票方案，在括号中的表示联票，短横线(-)用来分开乘车次序。//等号后输出的是该方案的花费数值。//////请编程解决上述问题。//注意：//1. 我们测试您的程序时，所用数据与题目中的示例数据不同，但格式完全一样。//2. 当多个方案有相同的最小花费，输出任意一个方案即可。//////要求考生把所有类写在一个文件中。//调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。//相关的工程文件不要拷入。请不要使用package语句。////另外，源程序中只能出现JDK1.5中允许的语法或调用。不能使用1.6或更高版本。public class Four {public static void main(String[] args){//线路对应站点ArrayList<String> a = bufferedReader();Map<String,ArrayList<String>> station = pathStation(a);//价格表Map<String,Integer> priceMap = bufferedReaderForPrice();//起点 终点String start = "五棵松";String end = "霍营";//获取所有的路线Set keys = station.keySet();Iterator iter = keys.iterator();ArrayList<String> way = new ArrayList<String>();while(iter.hasNext()){way.add(iter.next().toString());}// 在对应的路线中找站 先找到起点的线 -- - 然后找到终点的线----最后找两条线之间相同的线String startWay = "";String endWay = "";for(int i=0;i<way.size();i++){if(station.get(way.get(i)).contains(start)){ //该路线包含起点startWay = way.get(i);}if(station.get(way.get(i)).contains(end)){//该路线对应的是终点endWay = way.get(i);}}//在所有的线路中找到包含 endWay站台的路线String sameWay = "";String tempStart = "";String tempSame = "";String tempEnd = "";int sum = 710;for(int k=0;k<station.get(endWay).size();k++){//endWay 的所有站台String sta = station.get(endWay).get(k);for(int i=0;i<way.size();i++){int tempsum = 0;if(station.get(way.get(i)).contains(sta) && !station.get(way.get(i)).contains(end)){//找到一个包含 站台的路线 记录该路线sameWay = way.get(i);//System.out.println("起："+startWay+" 换乘："+sameWay+" 终："+endWay);//判断起点与换乘点的联票和换乘点与终点的联票的价格的最优// 有联票肯定买联票 ，联票一定比单票划算// 首先判断是否有联票 起--换// 两边的票价同时有联票的时候if(priceMap.containsKey(startWay+","+sameWay) && priceMap.containsKey(sameWay+","+endWay)){int a1 = priceMap.get(startWay+","+sameWay)+priceMap.get(endWay);int a2 = priceMap.get(sameWay+","+endWay)+priceMap.get(startWay);tempsum = a1>a2 ? a2:a1;}else if(priceMap.containsKey(sameWay+","+endWay)){tempsum = priceMap.get(sameWay+","+endWay)+priceMap.get(startWay);}else if(priceMap.containsKey(startWay+","+sameWay)){tempsum = priceMap.get(startWay+","+sameWay)+priceMap.get(endWay);}else{tempsum = priceMap.get(startWay)+priceMap.get(sameWay)+priceMap.get(endWay);}if(tempsum<sum){sum = tempsum;tempStart = startWay;tempEnd = endWay;tempSame = sameWay;}}}}//得到了确切的起点 换乘点 终点-(线1,线10)-线8 = 565if(priceMap.containsKey(tempStart+","+tempSame) && priceMap.containsKey(tempSame+","+tempEnd)){if((priceMap.get(tempStart+","+tempSame)>priceMap.get(tempSame+","+tempEnd))){System.out.println("-"+tempStart+"-("+tempSame+","+tempEnd+") = "+sum);}else{System.out.println("-("+tempStart+","+tempSame+")- "+tempEnd+" = "+sum);}}else if(priceMap.containsKey(tempStart+","+tempSame)){System.out.println("-("+tempStart+","+tempSame+")- "+tempEnd+" = "+sum);}else if(priceMap.containsKey(tempSame+","+tempEnd)){System.out.println("-"+tempStart+"-("+tempSame+","+tempEnd+") = "+sum);}else{System.out.println(tempStart+"-"+tempSame+"-"+tempEnd+" = " +sum);}}//处理所有的线路的信息public static Map<String,ArrayList<String>> pathStation(ArrayList<String> list){//将每条线路和自身的站相对应Map<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();ArrayList<String> temp = null;String path = "";String a = "0123456789";for (int i = 0; i < list.size(); i++) {String str = list.get(i);if(str.equals("")){continue;}if((str.charAt(0)+"").equals("线") && a.indexOf(str.charAt(1))!=-1){//为线路temp = new ArrayList<String>();path = list.get(i);map.put(path, null);}else{temp.add(list.get(i));map.put(path, temp);}}//for(int i=0;i<map.get("线2").size();i++){//System.out.println(map.get("线2").get(i));//}return map;}//读取文件中的信息public static ArrayList<String> bufferedReader(){//使用键字对进行数据的保存 键==线路名 值===站的集合ArrayList<String> list = new ArrayList<String>();File f = new File("src/com/stations.txt");try{BufferedReader br = new BufferedReader(new FileReader(f));while(br.ready()){list.add(br.readLine());}br.close();}catch(Exception ex){ex.printStackTrace();}return list;}//票价public static Map<String,Integer> bufferedReaderForPrice(){File f = new File("src/com/price.txt");//票价唯一 则：使用key-valueMap<String,Integer> map = new HashMap<String,Integer>();try{BufferedReader br = new BufferedReader(new FileReader(f));while(br.ready()){String temp = br.readLine();String[] arr = temp.split(" ");map.put(arr[0], Integer.parseInt(arr[1]));}br.close();}catch(Exception ex){ex.printStackTrace();}return map;}}