阅读下列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 20define N 50int a[N+1]; /*用于存放一条线路上的各站编号*/int g[N][N]; /*严存储对应的邻接矩阵*/int dist[N]; /*严存储站0到各站的最短路径*/int m, n;void buildG(){ int i, j, k, sc, ddprintf(“输入公交线路数,公交站数\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");elseprintf(“从0号站到%d站需换车%d次\n”,n-1,t);}
阅读下列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);
}