华为机试--地铁换乘问题

本文主要是介绍华为机试--地铁换乘问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

描述：已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。
地铁线A（环线）经过车站：A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10 A11 A12 A13 T2 A14 A15 A16 A17 A18
地铁线B（直线）经过车站：B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B1!0 T2 B11 B12 B13 B14 B15

输入：输入两个不同的站名

输出：所经过的站数及站的名称

其实分析问题就会发现，这是一个求最短路径的问题，是图算法的里面比较基础的。常见的求路径的有A星，Dijkstra算法,floyd算法等，由于研究的不深入，就不细谈了。floyd算法可参考http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html。

#include <iostream>
#include <string>
#include <stack>
using namespace std;
#define  inf 1000   //定义无穷远距离
#define  stationNum 35  //总的站台个数
string station[stationNum]={"A1","A2","A3","A4","A5","A6","A7","A8","A9","A10",  
"A11","A12","A13","A14","A15","A16","A17","A18",  
"B1","B2","B3","B4","B5","B6","B7","B8","B9","B10",  
"B11","B12","B13","B14","B15","T1","T2"} ; 
int string_To_int(string st);void Ford(int distance[][stationNum],int path[][stationNum]);int staNUm(int dis[][stationNum],int path[][stationNum],string start,string destination);void main()
{int path[stationNum][stationNum];int distance[stationNum][stationNum];Ford(distance,path);string start,des;cin>>start>>des;cout<<staNUm(distance,path,start,des);
}
int string_To_int(string st)
{for (int i=0;i<stationNum;i++){if (station[i]==st){return i;}}}void Ford(int distance[][stationNum],int path[][stationNum]){//距离矩阵初始化其中相邻两项边是联通的，其他边之间都是不通的for (int i=0;i<stationNum;i++){for (int j=0;j<stationNum;j++){if (i==j) distance[i][j]=0;else distance[i][j]=inf;}}int lineA[20]={0,1,2,3,4,5,6,7,8,33,9,10,11,12,34,13,14,15,16,17};int lineB[17]={18,19,20,21,22,33,23,24,25,26,27,34,28,29,30,31,32};for (int i=0;i<19;i++){distance[lineA[i]][lineA[i+1]]=1;distance[lineA[i+1]][lineA[i]]=1;}for (int i=0;i<16;i++){distance[lineB[i]][lineB[i+1]]=1;distance[lineB[i+1]][lineB[i]]=1;}//初始化pathfor (int i=0;i<stationNum;i++){for (int j=0;j<stationNum;j++){path[i][j]=i;}}for (int k=0;k<stationNum;k++)//注意K的位置！！！！{for (int j=0;j<stationNum;j++){for (int i=0;i<stationNum;i++){if (distance[i][j]>distance[i][k]+distance[k][j]){distance[i][j]=distance[i][k]+distance[k][j];path[i][j]=path[k][j];}}}}}int staNUm(int dis[][stationNum],int path[][stationNum],string start,string destination){int s=string_To_int(start);int d=string_To_int(destination);//因为path[i][j]存的是最后到达j的前一个站点，所以我们要输出路径，就要从后往前遍历path。存放在stack中，最后依次输出即可stack<int> s_stack;for (int i=0;i<stationNum;i++){for (int j=0;j<stationNum;j++){if (i==s&&j==d){ int k=j;do {k=path[i][k];s_stack.push(k);} while (k!=i);cout<<station[s_stack.top()];s_stack.pop();while (!s_stack.empty()){cout<<"->"<<station[s_stack.top()];s_stack.pop();}cout<<"->"<<station[j];cout<<endl;return dis[i][j]+1;}}}}

代码运行结果如下;

本文参考http://blog.csdn.net/qinhl060343/article/details/37819345

这篇关于华为机试--地铁换乘问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---