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;
}
}
分享到:
相关推荐
利用vs2010实现的数据结构课程设计题目,能够实现包含线路、站点信息的编辑和查询,换乘查询,支持文件数据的输入输出;能够实现二次换乘和时间最短查询。利用无向图的Dijkstra 算法实现查询;--cugxg...
C++ 地铁换乘程序实现 主要是提供一种C++实现的地铁换乘程序的实现方法
这是我在数据结构课上的期末大作业,使用C++实现了查找广州地铁换乘路线的程序,同时使用C++内置的windows API,实现了WINDOWS GUI图形界面。 下载仓库文件之后,可以点击exe文件直接运行程序。假如出现运行失败的...
【标题】: "简单广州地铁换乘系统" 是一个基于C++编程语言的课程设计项目,旨在模拟并解决广州市内一号线至八号线之间的地铁换乘问题。这个系统集成了各个地铁线路的站点信息,为用户提供便捷的换乘查询服务。 ...
基于迪杰斯特拉和A星算法的北京上海公交地铁换乘系统C++源码.zip 基于迪杰斯特拉和A星算法的北京上海公交地铁换乘系统C++源码.zip 基于迪杰斯特拉和A星算法的北京上海公交地铁换乘系统C++源码.zip 基于迪杰斯特拉和A...
北京地铁换乘查询系统查询系统主要包括调⑴用文件初始化地铁线路与图中的顶点函数,⑵初始化图的函数,⑶查看地铁线路详细信息函数,⑷在图中定位起始站与终点站的位置函数,⑸在地铁线路中判定每次经过的站始发为...
在本项目中,"基于QT5实现的上海市地铁换乘指南,数据结构"是一个结合了图形界面编程和数据结构的暑期课程设计。该程序利用QT5框架,通过Qt Creator 4.6.2开发环境来构建,旨在为用户提供上海市地铁线路的查询服务,...
该毕业设计项目是基于Qt框架实现的一个图形化上海地铁换乘系统。Qt是一个跨平台的C++图形用户界面应用程序开发框架,广泛应用于桌面、移动和嵌入式平台。通过使用Qt,开发者可以创建出功能丰富且具有良好用户体验的...
上海地铁换乘大全---21(最新版)
这种规划涉及到对地铁线路、站点、时刻表的管理和分析,以便为乘客提供最佳的换乘建议。这需要考虑到线路的繁忙程度、换乘时间、步行距离等多种因素。为了实现这一目标,系统通常采用图论中的最短路径算法,如...
【资源说明】 1、该资源内项目代码都是经过测试运行成功,功能正常的情况...基于Qt的图形化某海地铁换乘系统源码+项目说明+设计说明(支持查询两地铁站之间的最短路径和最少换乘路径,支持自主添加线路、站点等等).zip
在这个数据结构课程设计中,主题是“地铁换乘”,它主要关注如何利用数据结构和算法来解决实际生活中的交通路径规划问题。以下是基于这个课设的一些关键知识点: 1. **图数据结构**:地铁线路可以抽象为图,其中每...
地铁换乘算法 地铁查询算法的初步实现,仅供学习研究。 版权所有dzut@qq.com,如需转载,请保留版权。 查询注意事项: 1、应该简短输入,如:“罗湖”,不要输入“罗湖站”或“罗湖地铁站”。如要扩展,可自己二...
基于Dijkstra算法,JavaScript实现地铁换乘路线查询 基于Dijkstra算法,JavaScript实现地铁换乘路线查询 基于Dijkstra算法,JavaScript实现地铁换乘路线查询 基于Dijkstra算法,...
基于A星算法的城市地铁换乘导航系统设计与实现源码.zip基于A星算法的城市地铁换乘导航系统设计与实现源码.zip基于A星算法的城市地铁换乘导航系统设计与实现源码.zip基于A星算法的城市地铁换乘导航系统设计与实现源码...
标题“Chengtie.rar_java 地铁_北京地铁_地铁换乘”暗示这是一个与Java编程相关的项目,专注于创建一个能够模拟或展示北京市地铁系统及换乘情况的程序。描述中的“插入了音乐,生动直观”表明这个程序可能具有用户...
对每一个站点创建station对象(不同线路的换乘车站算不同的站点),每个站点的相邻点为其之前站点,之后站点,和换乘站点,换乘站点之间权值为0,然后建立邻接表,用狄杰斯特拉算法从起始站开始遍历,如果遍历到的...
《完善中国交通换乘枢纽-引入国际最佳实践 发展多式联运换乘枢纽》这份文件,由亚洲开发银行发布,旨在改善中国的交通换乘中心,借鉴并应用国际上的最佳实践经验,以推动多式联运换乘枢纽的发展,提高公共交通系统的...
基于A星算法的中国大陆城市地铁换乘导航系统源码+数据(人工智能大作业).zip基于A星算法的中国大陆城市地铁换乘导航系统源码+数据(人工智能大作业).zip基于A星算法的中国大陆城市地铁换乘导航系统源码+数据(人工...
这是我在数据结构课上的期末大作业,使用C++实现了查找广州地铁换乘路线的程序,同时使用C++内置的windows API,实现了WINDOWS GUI图形界面。下载仓库文件之后,可以点击exe文件直接运行程序。假如出现运行失败的...