无源最短路径之--地铁换乘

问题描述：

描述：已知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

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

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

这里用到了QUEUE容器，以及一个KNOWN记做访问过的路径，DIS就是到其他点的最短路径，这里我们用的是广度搜索优先的做法。

#include<stdio.h>
#include<string>
#include<queue>
using namespace std;

				  // a1 a2 a3 a3 a5 b1b2b3t1t2
int arc[10][10]={   0,1,0,0,1,  0,0,0,0,0,//a1
						1,0,0,0,0,  0,0,0,1,0,//a2
						0,0,0,1,0,  0,0,0,1,0,//a3
						0,0,1,0,0,  0,0,0,0,1,//a4
						1,0,0,0,0,  0,0,0,0,1,//a5

						0,0,0,0,0,  0,0,0,1,0,//b1
						0,0,0,0,0,  0,0,0,1,1,//b2
						0,0,0,0,0,  0,0,0,0,1,//b3
						0,1,1,0,0,  1,1,0,0,0,//t1
						0,0,0,1,1,  0,1,1,0,0};//t2

//地铁路线
/*     A2---- A1---- A5
		-			 -
 B1 --T1-----B2------T2-----B3
	  -				-
      A5------------A4
*/

int known[10];
int dis[10];
char label[10][10]={"A1","A2","A3","A4","A5","B1","B2","B3","T1","T2"};

int main()
{


	int n,m;
	queue<int> q;
	char a[10];
	char b[10];

	while(~scanf("%s %s",&a,&b))
	{
		//字符串转换
		for(int i=0;i<10;i++)
			if(!strcmp(a,label[i]))
				n=i;
		for(int i=0;i<10;i++)
			if(!strcmp(b,label[i]))
				m=i;

		for(int i=0;i<10;i++){
			known[i]=0;
			dis[i]=999;
		}

		q.push(n);
		dis[n]=0;

		while(!q.empty())
		{
			int v=q.front();
			q.pop();
			known[v]=1;

			for(int w=0;w<10;w++)
			{
				if(arc[v][w]==1&&dis[w]==999)
				{
					dis[w]=dis[v]+1;
					q.push(w);
				}
			}
		}
		printf("%d\n",dis[m]+1);
	}
	return 0;
}

无源最短路径之--地铁换乘

原文：http://blog.csdn.net/u013011841/article/details/44594007