未分类题

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。
【说明】设某城市有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)；
}