地铁换乘——华为2014校招机试样题
——方法一：Dijkstra最短路径算法
原题如下：
地铁换乘
描述:
已知2条地铁线路，其中A为环线，B为东西向线路，线路都是双向的。经过的站点名分别如下，两条线交叉的换乘点用T1、T2表示。编写程序，任意输入两个站点名称，输出乘坐地铁最少需要经过的车站数量（含输入的起点和终点，换乘站点只计算一次）。
地铁线A（环线）经过车站：A1 A2 A3 A4 A5 A6 A7 A8 A9 T1 A10A11 A12 A13 T2 A14 A15 A16 A17 A18
地铁线B（直线）经过车站：B1 B2 B3 B4 B5 T1 B6 B7 B8 B9 B10T2 B11 B12 B13 B14 B15
运行时间限制: 无限制
内存限制: 无限制
输入: 输入两个不同的站名
输出: 输出最少经过的站数,含输入的起点和终点，换乘站点只计算一次
样例输入: A1 A3
样例输出: 3
上星期试着解这道题，当时还没看数据结构图的部分，想着用双链表加上各种条件判断来解决，发现太复杂了，遂网上搜了搜，这里提供了一种通过图来解决的Floyed算法，链接如下：
http://blog.csdn.net/arcsinsin/article/details/11267755
鉴于此，这几天赶紧去看了下图的部分，刚看了Dijkstra单源点到所有终点的最短路径算法，想来可以改造下解决这里的问题，遂解决如下。
关于Dijkstra算法可以参见这里：
http://www.cnblogs.com/dolphin0520/archive/2011/08/26/2155202.html
#include <iostream>
#include <string>
#include <stack>
using namespace std;#define SIZE_A 21
#define SIZE_B 17#define N 35// 20 + 1
string A[] = {"A1","A2","A3","A4","A5","A6","A7","A8","A9","T1","A10","A11","A12","A13","T2","A14","A15","A16","A17","A18","A1"};
// 17
string B[] = {"B1","B2","B3","B4","B5","T1","B6","B7","B8","B9","B10","T2","B11","B12","B13","B14","B15"};
// 35
string Node[] = {"A1","A2","A3","A4","A5","A6","A7","A8","A9","T1","A10","A11","A12","A13","T2","A14","A15","A16","A17","A18","B1","B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14","B15"}; struct Graph {int matrix[N][N];int n;int e;
};Graph g;
bool s[N];
int dist[N];
int path[N];int length=0;string StrBegin,StrEnd;void Dijkstra(int v0, int v1);int GetPos(string *array, string & str)
{int n=0;if (str[0] == 'B') {n+=20;array+=20;}if (str == "T1") return 9;if (str == "T2") return 14;while (*array != str) {array ++;n++;}return n;
}void BuildGraph()
{// 初始化matrixfor (int i=0; i<N; i++){for (int j=0; j<N; j++){g.matrix[i][j]=0;}}// 根据A建立边信息for (int i=0; i<(SIZE_A-1); i++){int u = GetPos(Node,A[i]);int v = GetPos(Node,A[i+1]);g.matrix[u][v]=1;g.matrix[v][u]=1;}// 根据B建立边信息for (int i=0; i<(SIZE_B-1); i++){int u = GetPos(Node,B[i]);int v = GetPos(Node,B[i+1]);g.matrix[u][v]=1;g.matrix[v][u]=1;}int u = GetPos(Node,StrBegin);int v = GetPos(Node,StrEnd);Dijkstra(u,v);}void Dijkstra(int v0, int v1)
{// 1、初始化for (int i=0; i<N; i++) {s[i] = false;if (g.matrix[v0][i] != 0){dist[i] = g.matrix[v0][i];path[i] = v0;}else{dist[i] = INT_MAX;path[i] = -1;}}s[v0]=true;dist[v0]=0;path[v0]=v0;// 2、循环n-1次for (int i=0; i<(N-1); i++){// 2.1、取dist[u]最小的uint min=INT_MAX;int u;for (int j=0; j<N; j++){if (s[j] == false && dist[j] < min){min = dist[j];u = j;}}s[u] = true;// 2.2、更新u邻接的所有wfor (int w=0; w<N; w++){if (s[w] == false && g.matrix[u][w] != 0){if (dist[u] + g.matrix[u][w] < dist[w]){dist[w] = dist[u] + g.matrix[u][w];path[w] = u;}}}}// 3、获取结果while (v1 != v0){v1 = path[v1];length++;}length ++; //stack<int> s;//while (v1 != v0)//{// s.push(v1);// v1 = path[v1];//}//s.push(v0);//while (!s.empty())//{// length++;// if (1) // debug// {// int pos = s.top();// string str = Node[pos];// str += "\0";// cout<<str<<" ";// }// s.pop();//}
}int main()
{//while(0){length = 0;cin>>StrBegin>>StrEnd;if (StrBegin == StrEnd)cout<<"1"<<endl;else{BuildGraph();cout<<length<<endl;} system("pause");}return 0;
}——方法二：Floyd-Warshall顶点对最短路径算法
该算法可以求出各顶点对之间的最短路径，写法简单，主要核心就是一个三层嵌套循环即可。
#include <iostream>
#include <string>
#include <stack>
using namespace std;#define SIZE_A 21
#define SIZE_B 17#define N 35
#define INF 0xfffff// 20 + 1
string A[] = {"A1","A2","A3","A4","A5","A6","A7","A8","A9","T1","A10","A11","A12","A13","T2","A14","A15","A16","A17","A18","A1"};
// 17
string B[] = {"B1","B2","B3","B4","B5","T1","B6","B7","B8","B9","B10","T2","B11","B12","B13","B14","B15"};
// 35
string Node[] = {"A1","A2","A3","A4","A5","A6","A7","A8","A9","T1","A10","A11","A12","A13","T2","A14","A15","A16","A17","A18","B1","B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14","B15"}; int matrix[N][N];int dist[N][N];
int path[N][N];int length=0;string StrBegin,StrEnd;void Floyd_Warshall();int GetPos(string *array, string & str)
{int n=0;if (str[0] == 'B') {n+=20;array+=20;}if (str == "T1") return 9;if (str == "T2") return 14;while (*array != str) {array ++;n++;}return n;
}void BuildGraph()
{// 初始化matrixfor (int i=0; i<N; i++){for (int j=0; j<N; j++){matrix[i][j]=0;}}// 根据A建立边信息for (int i=0; i<(SIZE_A-1); i++){int u = GetPos(Node,A[i]);int v = GetPos(Node,A[i+1]);matrix[u][v]=1;matrix[v][u]=1;}// 根据B建立边信息for (int i=0; i<(SIZE_B-1); i++){int u = GetPos(Node,B[i]);int v = GetPos(Node,B[i+1]);matrix[u][v]=1;matrix[v][u]=1;}int u = GetPos(Node,StrBegin);int v = GetPos(Node,StrEnd);Floyd_Warshall();}void Floyd_Warshall()
{// 1、初始化for (int i=0; i<N; i++){for (int j=0; j<N; j++){if( i != j && matrix[i][j] > 0){dist[i][j] = matrix[i][j];path[i][j] = i;}else{dist[i][j] = INF;path[i][j] = -1;}}}// 2、Floyd核心三层循环for (int k=0; k<N; k++){for (int i=0; i<N; i++){for (int j=0; j<N; j++){if (dist[i][j] > dist[i][k] + dist[k][j]){dist[i][j] = dist[i][k] + dist[k][j];path[i][j] = path[k][j];}}}}// 3、输出结果int u = GetPos(Node,StrBegin);int v = GetPos(Node,StrEnd);while (u != v){v = path[u][v];length++;}length ++;
}int main()
{//while(0){length = 0;cin>>StrBegin>>StrEnd;if (StrBegin == StrEnd)cout<<"1"<<endl;else{BuildGraph();cout<<length<<endl;} system("pause");}return 0;
}
