地铁换乘-取绝佳路线最低票价
地铁换乘-取最佳路线最低票价
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 = 565
if(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-value
Map<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;
}
}