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