#include <stdio.h>
#include <stdlib.h>
#define INFINITY 9999
#define MAXVNUM 30
char ans;
typedef struct
{
 int Vnum;
 int arcs[MAXVNUM][MAXVNUM];            //圖的存儲結(jié)構(gòu)為鄰接矩陣
}Graph;
int createGraph(Graph *g,int *start,int *end)
{
 int n,m,i,j,k,s,count;
 int t[MAXVNUM];
 printf("\n★ 請輸入公交車站數(shù)和公交車數(shù):\n");
 scanf("%d %d",&n,&m);
 if(n<=1 || m<1)
  return -1;
 g->Vnum = n;
 for(i=0;i<n;i++)
  for(j=0;j<n;j++)
   g->arcs[i][j] = INFINITY;    //鄰接矩陣初始化
 for(s=0;s<m;s++)
 {
  printf("\n▲請輸入第%d輛公交車所途經(jīng)各站的編號【0<=編號<=%d,-1結(jié)束】:\n",s+1,n-1);
  scanf("%d",&k);
  count = 0;
  while(k!=-1)
  {
   t[count++]=k;
   scanf("%d",&k);
  }
  for(i=0;i<count-1;i++)
  {
   for(j=i+1;j<count;j++)        //當(dāng)前線路中，從t[i]到t[j]有直達(dá)公交車
    g->arcs[t[i]][t[j]]=1;
  }
 }
 printf("\n★ 請輸入上車站編號和下車站編號【0<=編號<=%d】:\n",n-1);
 scanf("%d%d",start,end);
 if( *start<0 || *start>n-1 || *end<0 || *end>n-1)
  return -1;
 return 0;
}
int findMinmum(Graph g,int start,int end)   //迪杰斯特拉算法找最小上車次數(shù)
{
 int s[MAXVNUM];
 int i,j,u,*dist,min;
 if(start==end)
  return 0;
 dist=(int *)malloc(sizeof(int));
 if(dist==NULL)
  return -1;
 for(i=0;i<g.Vnum;i++)
 {
  dist[i]=g.arcs[start][i];    //從start可直達(dá)的站點(diǎn)上車次數(shù)置1
  s[i]=0;       //所有站點(diǎn)的上車次數(shù)還未找到
 }
 s[start]=1;   //已經(jīng)找到站點(diǎn)start的最少上車次數(shù)
 dist[start]=0;   //從站點(diǎn)start到start的最少上車次數(shù)初始化為0
 for(i=0;i<g.Vnum;++i)
 {
  min=INFINITY;
  u=start;
  for(j=0;j<g.Vnum;++j)  //u是從start出發(fā)能夠到達(dá)的所有站點(diǎn)中上車次數(shù)最少者
  {
   if(s[j]==0 && dist[j]<min)
   {
    min=dist[j];
    u=j;
   }
  }
  s[u]=1;    //已經(jīng)找到從站點(diǎn)start到u的最少上車次數(shù)，將u加入集合s
  for(j=0;j<g.Vnum;++j)   //更新當(dāng)前情況下其他站點(diǎn)的最少上車次數(shù)
  {
   if(s[j]==0 && min+g.arcs[u][j]<dist[j])
    dist[j]=min+g.arcs[u][j];
  }
 }
 return dist[end];
}
int main(void)
{
 int start,end,m;
 printf("\n說明：");
 printf("\n\t您好！歡迎使用該系統(tǒng)！\n");
 printf("\t[一]  本系統(tǒng)是根據(jù)有向圖創(chuàng)建的，請先輸入你想乘車地點(diǎn)到目的地共有多少站和該地點(diǎn)的公交車數(shù)量。站數(shù)相當(dāng)于有向圖中的頂點(diǎn)數(shù)。\n");
 printf("\t[二]  請輸入每條公交車所路徑的站點(diǎn)，相當(dāng)于有向圖中連接每條邊的頂點(diǎn)。輸入完后按-1進(jìn)入下一輛公交車的路徑。\n ");
 printf("\t[三]  請輸入上車地點(diǎn)的站編號和下車站的編號，相當(dāng)于有向圖中任意的兩個(gè)頂點(diǎn)。輸入完后系統(tǒng)將會根據(jù)所輸入的信息輸出最少換車次數(shù)。\n ");
 do
 {
  Graph G;
  if(createGraph(&G,&start,&end)==-1)
  {
   printf("\n     真遺憾!\n    創(chuàng)建有向圖失敗!   \n    請重新輸入數(shù)據(jù) !\n");
   return 0;
  }
  m=findMinmum(G,start,end);
  if(m<INFINITY)
   printf(" 恭喜!\n  有車可以到達(dá)該目的地\n  從上車站%d到下車站%d的最少換車次數(shù)為：  %d\n",start,end,m-1);
  else
   printf("\n對不起!\n沒有相應(yīng)的公交車可以到達(dá)該站點(diǎn) !\n");
  printf("\n是否繼續(xù)呢(y/n)?");
  fflush(stdin);
  ans=getchar();
  system("cls");
 }while(ans=='y' || ans=='Y');
 printf("\n-----------------------謝謝你使用該系統(tǒng)！----------------------------");
 system("pause");
 return 0;
}