公交车.c

来自「C++经典算法之 公交算法 常用算法 方便使用」· C语言 代码 · 共 65 行

#include<stdio.h>
#define N 50
#define M 20

int g[N][N];
int a[N+1],dist[N],m,n;

void buildG()
{
   int i,j,k,sc,dd;
   printf("输入公交线路数，公交站数\n");
   scanf("%d,%d",&m,&n);
   for(i=0;i<n;i++)
	   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) a[sc++]=dd;
	   }
	   a[sc]=-1;
	   for(k=1;a[k]>=0;k++)
		   for(j=0;j<k;j++)
			   g[a[j]][a[k]]=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++)
			if(dist[j]>0&&(k==-1||dist[j]<dist[k])) k=j;
		if(k<0||k==n-1) break;
		dist[k]=-dist[k];
		for(j=1;j<n;j++)
			if(dist[j]>=0&&g[k][j]==1&&(dist[j]==0||-dist[k]+1<dist[j]))
				dist[j]=-dist[k]+1;
	} while(1);
	j=dist[n-1];
	return k<0?-1:j-1;
}

void main()
{
	int t;
	buildG();
	if ((t=minlen())<0) 
	{
     printf("无解！\n");
	} 
	else
	{
     printf("从0号站到%d站需要换车%d次\n",n-1,t);
	}
	

}