公交最少换车次数_公交换乘最后一公里

公交最少换车次数由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“公交换乘最后一公里”。

设一个城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。现要求编制程序，输入城市的公交线路数、车站个数，以及各共交线路上的站号，求站0至站n-1的最少换车次数。

程序利用输入信息构建一张有向图G，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边。如是这样，从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路经长度。而程序要求的换车次数就是上车次数减1。

#include #include int * buildG(int *np){ int n, m, sc, i, j, k;char ch;int *s, *g;

printf(“输入车站个数和公交线路条数：

”);

scanf(“%d%d”, &n, &m);

g =(int *)malloc(sizeof(int)*n*n);

for(i = 0;i

g[i] = 0;

s =(int *)malloc(sizeof(int)*n);

for(i = 0;i

printf(“输入第%d条公交车线路的各站编号（0

printf(”要求在线路的最后一个站号输入后紧接输入回车。n“);

sc = 0;/* 当前线路站计数器 */

ch = ' ';/* 存储站号后的字符，初态预置空格符 */

while(ch!= 'n')/* 站号后字符不是回车符循环 */

scanf(”%d%c“, &s[sc++], &ch);

for(j = 0;j

if(s[j] = n)break;

if(j

printf(”输入错误，该线路重新输入n“);i--;continue;

}

for(k = 1;k

for(j = 0;j

*(g + s[j]*n + s[k])= 1;

}

free(s);

*np = n;

return g;

}

int minLen(int *g, int n)

{ int j, k, *dist;

if(n == 0)return 0;

dist =(int *)malloc(sizeof(int)* n);/* 存储到各站的上车次数 */

for(j = 0;j

dist[j] = g[j];

dist[0] = 1;/* 若dist[i]

do { /* 每循环一次计算到一个站的换车次数 */

for(k =-1, j = 0;j

if(dist[j] > 0 &&(k ==-1 || dist[j]

k = j;

if(k

break;/* 找不到未处理的车站，或确定了n-1站的上车次数 */

dist[k] =-dist[k];/* 设置k站已求得上车次数的标记 */

for(j = 1;j

if(dist[j] >= 0 && *(g+k*n+j)&&(dist[j] == 0 ||-dist[k] + 1

dist[j] =-dist[k] + 1;

} while(1);

j = dist[n-1];

free(dist);

return k

}

void main()

{ int *g , t, n;

g = buildG(&n);

if((t = minLen(g, n))

else printf(”从0号站到%d站需换车%d次n", n-1, t);

free(g);

}