设某城市有 n 个车站，并有 m 条公交线路连接这些车站，设这些公交车都是单向
的，这 n 个车站被顺序编号为 0 至 n-1 。本程序，输入该城市的公交线路数、车站个
数，以及各公交线路上的各站编号，求得从站 0 出发乘公交车至站 n-1 的最少换车次数。
程序利用输入信息构建一张有向图 G (用邻接矩阵 g 表示)，有向图的顶点是车站，
若有某条公交线路经 i 站能到达 j 站，就在顶点 i 到顶点 j 之间设置一条权为 1 的有向
边&lti,j>。如是这样，从站点 x 至站点 y 的最少上车次数便对应图 G 中从点 x 至点 y 的
最短路径长度。而程序要求的换车次数就是上车次数减 1 。
[程序6]
#include &ltstdio.h>
#define M 20
#define N 50
int a[N+l];
/*用于存放一条线路上的各站编号*/
int g[N][N];
/*存储对应的邻接矩阵*/
int dist[N];
/*存储站 0 到各站的最短路径*/
int m, n;
void buildG( )
{ int i, j, k, sc, dd;
printf ("输入公交线路数，公交站数/n");
scanf ("%d%d", &ampm, &ampn);
for( i = O;
i < n;
i++) /* 邻接矩阵清0 */
for(j = O;
j < n;
j++) g[j] = O;
for( i = O;
i < m;
i++) {
printf (" 沿第 %d 条公交车线路前进方向的各站编号
( O <= 编号 <= %d, -1 结束):/n", i+l, n-1 );
sc = O;
/* 当前线路站计数器 */
while (1) {
scanf ("%d", &ampdd);
if (dd == -1) break;
if (dd >= 0 &&
dd < n) a[sc++]=dd;
}
a[sc] = -1;
for(k = 1;
a[k] >= O;
k++) /* 处理第 i+l 条公交线路 */
for (j = 0;
j < k;
j++)
g[ a[j] ][ a[k] ] = 1;
}
}
int minLen( )
{ int j, k;
for(j = O;
j < n;
j++) dist[j] = g[O][j];
dist[O] = 1;
do
{
for(k = -1, j = 0 ;
j < n;
j++) /* 找下一个最少上车次数的站*/
if (dist[j] > 0 &&
(k == -1 || dist[j] < dist[k])) k = j;
if (k < 0 || k == n-l) break;
dist[k] = -dist[k];
/* 设置 k 站已求得上车次数的标记 */
for(j = 1;
j < n;
j++) /* 调整经过 k 站能到达的其余各站的上车次数 */
if ( (dist[j]>=0)&&(g[j][k]==1) &&
(dist[j] == 0 || -dist[k] + 1 < dist[j] ) )
dist[j] = -dist[k]+1 ;
} while (1);
j = dist [n-l];
return k<0?-1:j-1 ;
}
void main ( )
{ int t;
buildG ( );
if ((t = minLen()) < O) printf ("无解 ! /n"),
else
printf ("从 0 号站到 %d 站需换车 %d 次/n , n-i, t);
}
