无源最短路径之--地铁换乘
发布时间
阅读量：
阅读量
问题描述：
现有两条地铁线路运营中：线路A为单一环形轨道运行模式（环线），而线路B则为东西走向的直线型轨道布局（直线）。两条线路均采用双向通行模式运行。其中一条线路环绕全城运行（环线），另一条则自西向东直通南北方向（直线）。每条线路均设有多个站点作为乘客上下车的位置选择点，并在特定位置设置了换乘站以方便不同线路间的交通联系。
输入：输入两个不同的站名
输出：所经过的站数及站的名称
在本实现中使用了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;
}全部评论 (0)
还没有任何评论哟~