#include <iostream> 
#include <fstream> 
#include <time.h> 
#include <stdio.h> 
#include <cstring> 
#include <iomanip> 
#include <stack> 
#include <queue> 
#define MAX 20 
#define MAX2 2 
#define INFINITY 32767 
int arr1[MAX][MAX]; 
 
using namespace std; 
double arr[MAX][MAX]; 
 
class ArcNode { 
 public: 
 int adjvex; 
 ArcNode *nextarc; 
 double weight; 
}; 
 
 
class VNode { 
 public: 
 string data1; 
 string data2; 
 int wel; 
 bool wc; 
 bool rest; 
 ArcNode *firstarc; 
}; 
 
class ALGraph { 
 public: 
 VNode *vertices; 
 int vexnum, arcnum; 
 ArcNode *arcNode; 
}; 
 
class zanlind 
{ 
public: 
 int number; 
 int hour; 
 int minute; 
}; 
 
 
int LocateVex(ALGraph G, string v) { 
 int i; 
 for(i = 0; v != G.vertices[i].data1 && i < G.vexnum; i++) 
 ; 
 if(i >= G.vexnum) 
 return -1; 
 return i; 
} 
 
int LocateW(ALGraph G, int wel) { 
 int i; 
 for(i = 0; wel != G.vertices[i].wel && i < G.vexnum; i++) 
 ; 
 if(i >= G.vexnum) 
 return -1; 
 return i; 
} 
 
void CreateUDN(ALGraph &G) { 
 G.arcNode=new ArcNode[MAX]; 
 G.vertices=new VNode[MAX]; 
 
 fstream file("info.txt"); 
 if(file.fail()) 
 { 
 cout << "error open!" << endl; 
 } 
 int j; 
 ArcNode *s, *t; 
 cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)："; 
 cin>>G.vexnum>>G.arcnum; 
 int i=0; 
 cout<<endl; 
 while(!file.eof()) 
 { 
 file >>G.vertices[i].data1>>G.vertices[i].data2 >> 
 G.vertices[i].wel>> G.vertices[i].rest>>G.vertices[i].wc; 
 G.vertices[i].firstarc = NULL; 
 i++; 
 } 
 cout<<endl; 
 fstream file1("edge.txt"); 
 if(file.fail()) 
 { 
 cout << "error open!" << endl; 
 } 
 while(!file1.eof()) 
 { 
 int weight; 
 string v1, v2; 
 file1>>v1>>v2>>weight; 
  
 int i = LocateVex(G, v1); 
 int j = LocateVex(G, v2); 
 
 s = new ArcNode(); 
 t = new ArcNode(); 
 
 s->adjvex = j; 
 s->nextarc = G.vertices[i].firstarc; 
 s->weight=weight; 
 G.vertices[i].firstarc =s; 
 
 t->adjvex = i; 
 t->nextarc = G.vertices[j].firstarc; 
 t->weight=weight; 
 G.vertices[j].firstarc =t; 
 } 
 file1.close(); 
 file.close(); 
 
} 
 
 
void PrintAdjList(ALGraph &G) { 
 cout<<"下面是圖的鄰接鏈表輸出：" <<endl; 
 ArcNode *p; 
 cout<<" 編號(hào) "<<"頂點(diǎn)"<<" 相鄰邊編號(hào)"<<endl; 
 for(int i = 0; i < G.vexnum; i++) { 
 cout<<" "<<i<<" "<<G.vertices[i].data1; 
 for(p = G.vertices[i].firstarc; p; p = p->nextarc) 
  cout<<"--------->"<<p->adjvex; 
 cout<<endl; 
 } 
 
 
} 
 
void OutputGraph(ALGraph G) { 
 cout<<"下面是圖的鄰接矩陣輸出："<<endl; 
 int m1=G.vexnum; 
 int m2=G.vexnum; 
 
 for(int i=0; i<m1; i++) { 
 for(int j=0; j<m2; j++) { 
  arr[i][j]=32767; 
 } 
 } 
 
 for(int k=0; k<m1; k++) { 
 ArcNode *p=G.vertices[k].firstarc; 
 for(int i2=0; i2<m2; i2++) { 
  if(k==i2) { 
  arr[k][i2]=0; 
  } 
  if(p) { 
  arr[k][p->adjvex]=p->weight; 
  p=p->nextarc; 
  } 
 
 } 
 } 
 cout<<" "; 
 for(int n1=0; n1<m1; n1++) { 
 cout<<setiosflags(ios::left)<<setw(11)<<G.vertices[n1].data1; 
 
 } 
 cout<<endl; 
 for(int n2=0; n2<m1; n2++) { 
 cout<<setiosflags(ios::left)<<setw(10)<<G.vertices[n2].data1; 
 for(int n3=0; n3<m1; n3++) { 
  cout<<setiosflags(ios::left)<<setw(10)<<arr[n2][n3]; 
 
 } 
 cout<<endl; 
 
 
 } 
 
 
} 
 
bool visited[MAX]; 
stack<int> *s=new stack<int>(); 
 
bool isOver(ALGraph G,bool a[MAX]) { 
 for(int i=0; i<G.vexnum; i++) { 
 if(a[i]!=1) { 
  return false; 
 } 
 } 
 return true; 
 
 
} 
 
void DFSTraverse(ALGraph G) 
{ 
 bool sta[20]; 
 int v; 
 for (v = 0; v<G.vexnum; v++) 
 { 
 sta[v] =true; 
 } 
 stack<int>status; 
 int n=0; 
 int num = -1; 
 int pk; 
 ArcNode *e; 
 cout << G.vertices[0].data1 << "->"; 
 sta[0] =false; 
 status.push(0); 
 int aa, bb; 
 aa = 0; 
 
 while (n < G.vexnum-1){ 
  e = NULL; 
  num = status.top(); 
  e = G.vertices[num].firstarc; 
  while (e){ 
  if (sta[e->adjvex] == false){ 
   e = e->nextarc; 
  } 
  else{ 
   status.push(e->adjvex); 
   cout << G.vertices[e->adjvex].data1<<"->"; 
   aa = e->adjvex; 
   sta[e->adjvex] = false; 
   n++; 
   break; 
  } 
   } 
  if (e == NULL){ 
  pk = status.top(); 
  bb = pk; 
  if (aa != bb){ 
   cout << G.vertices[pk].data1<<"->"; 
  } 
  
  status.pop(); 
  } 
  if (status.top() == 0){ 
  cout << G.vertices[0].data1 << "->"; 
  } 
 } 
 cout << endl; 
} 
 
bool IsEdge(ALGraph G) { 
 string s1, s2; 
 cin>>s1>>s2; 
 int iA=LocateVex(G,s1); 
 int jA=LocateVex(G,s2); 
 
 ArcNode *p=G.vertices[iA].firstarc; 
 while(p) { 
 if(p->adjvex==jA) { 
  return 1; 
 } else { 
  p=p->nextarc; 
 } 
 } 
 return 0; 
 
 
} 
 
int adjlist[MAX]; 
void FindInDegree( ALGraph &g) { 
 int i; 
 ArcNode *p; 
 for (i=0; i<g.vexnum; i++) 
 adjlist[i]=0; 
 for (i=0; i<g.vexnum; i++) { 
 p=g.vertices[i].firstarc; 
 while(p) { 
  adjlist[p->adjvex]++; 
  p=p->nextarc; 
 } 
 } 
} 
void JudgeCir(ALGraph G) { 
 FindInDegree(G); 
 int count=0; 
 int Q[MAX]; 
 int front,rear,v; 
 front=rear=-1; 
 for(int i=0; i<G.vexnum; i++) { 
 if((adjlist[i]==0)||(adjlist[i]==1)) { 
  Q[++rear]=i; 
  count++; 
 } 
 } 
 
 while(front!=rear) { 
 v=Q[++front]; 
 if(adjlist[v]==1) { 
  adjlist[v]=-1; 
  for(int j=0; j<G.vexnum; j++) { 
  if(arr[v][j]>0 && arr[v][j]<32767) { 
   adjlist[j]--; 
   if(adjlist[j]==1) { 
   Q[++rear]=j; 
   count++; 
   } 
  } 
  } 
 } else { 
  adjlist[v]=-1; 
 } 
 } 
 
 if(count<G.vexnum) { 
 cout<<"圖中有回路"<<endl; 
 } else 
 cout<<"圖中無回路"<<endl; 
} 
 
int in[MAX]; 
 
void LocateVex2(ALGraph G, string v) { 
 for(int i = 0;i < MAX; i++) 
 { 
 in[i]=10000; 
 } 
 for(int i = 0;i < G.vexnum; i++) 
 { 
 if(G.vertices[i].data1.find(v)<G.vertices[i].data1.length() || 
 G.vertices[i].data2.find(v)<G.vertices[i].data2.length()) 
 { 
  in[i]=i; 
 } 
 } 
} 
 
void Search(ALGraph G,string s) { 
 FindInDegree(G); 
 LocateVex2(G, s); 
 for(int i=0;i<G.vexnum;i++) 
 { 
 if(in[i]!=10000) 
 { 
  cout<<"您所要查詢的景點(diǎn)介紹為："<<endl 
  <<endl<<"該景點(diǎn)名字是：" 
  <<G.vertices[in[i]].data1 
  <<" "<<endl 
  <<"該景點(diǎn)介紹為："<<G.vertices[in[i]].data2<<endl 
  <<"該景點(diǎn)歡迎度為：" 
  <<G.vertices[in[i]].wel<<endl<<"有無休息區(qū)為：" 
  <<G.vertices[in[i]].rest 
  <<endl<<"有無廁所為："<<G.vertices[in[i]].wc 
  <<endl<<endl; 
 } 
 
 } 
 
} 
 
void SortWel(ALGraph G) { 
 int ary[G.vexnum]; 
 
 for(int i=0; i<G.vexnum; i++) { 
 ary[i]=G.vertices[i].wel; 
 } 
 
 int i, j, tmp; 
 for(i=0; i<G.vexnum; i++) { 
 tmp = ary[i]; 
 for(j=G.vexnum-1; j>i; j--) { 
  if(tmp < ary[j]) { 
  ary[i] = ary[j]; 
  ary[j] = tmp; 
  tmp = ary[i]; 
  } 
 } 
 } 
 
 for(int j=0; j<G.vexnum; j++) { 
 int m=LocateW(G,ary[j]); 
 cout<<j+1<<"、 "<<G.vertices[m].data1<<endl; 
 } 
} 
 
bool isInN(ALGraph G,int a[MAX],int n) 
{ 
 for(int i=0;i<G.vexnum;i++) 
 { 
 if(a[i]==n) 
 { 
  return true; 
 } 
 } 
 return false; 
} 
 
void SortN(ALGraph G) { 
 int ary[G.vexnum]; 
 int a[G.vexnum]; 
 
 for(int j=0; j<G.vexnum; j++) { 
 a[j]=10000; 
 } 
 
 FindInDegree(G); 
 for(int i=0; i<G.vexnum; i++) { 
 ary[i]=adjlist[i]; 
 } 
 
 int i, j, tmp; 
 for(i=0; i<G.vexnum; i++) { 
 tmp = ary[i]; 
  
 for(j=G.vexnum-1; j>i; j--) { 
  if(tmp <= ary[j]) { 
  a[i]=j; 
  ary[i] = ary[j]; 
  a[i]=j; 
  ary[j] = tmp; 
  tmp = ary[i]; 
  } 
  
  
 } 
 } 
 
 for(int j=0;j<G.vexnum;j++) 
 { 
 for(int i=0;i<G.vexnum;i++) 
 { 
  if(ary[j]==adjlist[i]) 
  { 
  if(!isInN(G,a,i)) 
  { 
   a[j]=i; 
  } 
  else 
  { 
   continue; 
  } 
  } 
 } 
 } 
 for(int i=0;i<G.vexnum;i++) 
 { 
 cout<<i+1<<"、"<<G.vertices[a[i]].data1<<endl; 
 } 
 
 
} 
 
void ShortestPath_DIJ(ALGraph G,int v0, int p[][MAX], int D[]) { 
 int v, w, i, j, min; 
 bool final[10]; 
 for(v=0; v<G.vexnum; v++) { 
 final[v]=false; 
 D[v]=arr[v0][v]; 
 for(w=0; w<G.vexnum; w++) 
  p[v][w]=-1; 
 if(D[v]<INFINITY) { 
  p[v][0]=v0; 
  p[v][1]=v; 
 } 
 } 
 
 D[v0]=0; 
 final[v0]=true; 
 
 for(i=1; i<G.vexnum; i++) { 
 min=INFINITY; 
 for(w=0; w<G.vexnum; w++) 
  if(!final[w] && D[w]<min) { 
  v=w; 
  min=D[w]; 
  } 
 final[v]=true; 
 for(w=0; w<G.vexnum; w++) { 
  if(!final[w] && min<INFINITY && arr[v][w]<INFINITY 
  && (min+arr[v][w]<D[w])) { 
  D[w]=min+arr[v][w]; 
  for(j=0; j<G.vexnum; j++) { 
   p[w][j]=p[v][j]; 
   if(p[w][j]==-1) { 
   p[w][j]=w; 
   break; 
   } 
  } 
 
  } 
 } 
 } 
} 
 
bool isInVe(ALGraph G,string va) 
{ 
 for(int i=0;i<G.vexnum;i++) 
 { 
 if(G.vertices[i].data1==va) 
 { 
  return true; 
 } 
 } 
 return false; 
} 
 
void printShortestPath(ALGraph G) 
{ 
 
 int iA,jA; 
 string s1,s2; 
 int p[MAX][MAX]; 
 int D[MAX]; 
 cout<<"請輸入要查詢距離的兩個(gè)景點(diǎn)的名稱："; 
 cin>>s1>>s2; 
 if(isInVe(G,s1) && isInVe(G,s2)) 
 { 
 iA=LocateVex(G,s1); 
 jA=LocateVex(G,s2); 
 ShortestPath_DIJ(G,iA, p, D); 
 cout<<"到各頂點(diǎn)的最短路徑及長度為："<<endl; 
  
 if(jA!=0 && D[jA]!=INFINITY) { 
  cout<<"最短路徑為："; 
  for(int j=0; j<G.vexnum; j++) { 
  if(p[jA][j]>-1) 
   cout<<G.vertices[p[jA][j]].data1 
   <<" "; 
  } 
  cout<<endl; 
  cout<<"最短距離為:"<<D[jA]; 
 } else if(D[jA]==INFINITY) 
   cout<<G.vertices[iA].data1<<"-" 
   <<G.vertices[jA].data1 
   <<":"<<"不可達(dá)"<<endl; 
 } 
 else 
 { 
 cout<<"您輸入的景點(diǎn)名稱不存在，請輸入正確的景點(diǎn)名稱："<<endl; 
 printShortestPath(G); 
 } 
 
 } 
 
void prim(ALGraph G,int v,double arr[MAX][MAX]) { 
 
 int lowcost[MAX]; 
 int min; 
 int closest[MAX],i,j,k; 
 for(i=0; i<G.vexnum; i++) { 
 lowcost[i]=arr[v][i]; 
 closest[i]=v; 
 } 
 for(i=1; i<G.vexnum; i++) { 
 min=INFINITY; 
 for(j=0; j<G.vexnum; j++) { 
  if(lowcost[j]!=0&&lowcost[j]<min) { 
  min=lowcost[j]; 
  k=j; 
  } 
 } 
 cout<<"從"<<G.vertices[closest[k]].data1<<"到" 
 <<G.vertices[k].data1<<"修一條路"<<endl; 
 lowcost[k]=0; 
 
 for(j=0; j<G.vexnum; j++) { 
  if(arr[k][j]!=0 && arr[k][j]<lowcost[j]) { 
  lowcost[j]=arr[k][j]; 
  closest[j]=k; 
  } 
 } 
 
 } 
} 
 
stack<zanlind> parking; 
stack<zanlind> cars; 
queue<zanlind> waits; 
int z[MAX2]; 
bool isInZan(int zan[],int number) 
{ 
 for(int i=0;i<MAX2;i++) 
 { 
 if(zan[i]==number) 
 { 
  return true; 
 } 
 } 
 return false; 
} 
 
int indexZ(int z[],int n) 
{ 
 for(int i=0;i<MAX2;i++) 
 { 
 if(z[i]==n) 
 { 
  return i; 
 } 
 } 
 return -1; 
} 
void goIn() 
{ 
 int k1=0; 
 zanlind zan; 
 cout<<"車牌號(hào)為："; 
 cin>>zan.number; 
 cout<<endl; 
 /* 
 time_t t = time(0); 
 char tmp[64]; 
 strftime(tmp,sizeof(tmp),"%X ",localtime(&t)); 
 zan.time=tmp; 
 */ 
 struct tm *newtime; 
 time_t long_time; 
 time( &long_time ); //Get time as long integer 
 newtime = localtime( &long_time ); 
 int h = newtime->tm_hour;//得到當(dāng)前時(shí)間的小時(shí) 
 int m = newtime->tm_min;//得到當(dāng)前時(shí)間的分鐘 
 zan.hour=h; 
 zan.minute=m; 
 
 
 cout<<"進(jìn)場時(shí)間為："; 
 if(zan.minute>=1 && zan.minute<10) 
 { 
 cout<<zan.hour<<":0"<<zan.minute<<endl; 
 } 
 else 
 { 
 cout<<zan.hour<<":"<<zan.minute<<endl; 
 } 
 
 
 if(parking.size()<MAX2) 
 { 
 for(int m=0;m<MAX2;m++) 
 { 
  if(z[m]==0) 
  { 
  z[m]=zan.number; 
  break; 
  } 
 } 
 parking.push(zan); 
 cout<<"該車已進(jìn)入停車場在： "<<k1++<<"號(hào)車道"; 
 } 
 else 
 { 
 cout<<"停車場已滿，請等待其他車輛離開："; 
 waits.push(zan); 
 } 
} 
 
void goOut() 
{ 
 if(parking.size()<=0) 
 { 
 cout<<"停車場為空，沒有車要離開！"; 
 } 
 else 
 { 
 cout<<"請輸入您的車牌號(hào)："; 
 int number; 
 cin>>number; 
 if(isInZan(z,number)) 
 { 
  while(parking.top().number!=number) 
  { 
  cars.push(parking.top()); 
  parking.pop(); 
  } 
  
  int num=indexZ(z,parking.top().number); 
  z[num]=0; 
  /* 
  time_t t = time(0); 
  char tmp[64]; 
  strftime(tmp,sizeof(tmp),"%X ",localtime(&t)); 
  */ 
  struct tm *newtime; 
  time_t long_time; 
  time( &long_time ); //Get time as long integer 
  newtime = localtime( &long_time ); 
  int h = newtime->tm_hour;//得到當(dāng)前時(shí)間的小時(shí) 
  int m = newtime->tm_min;//得到當(dāng)前時(shí)間的分鐘 
  cout<<"車牌號(hào)為："<<parking.top().number<<"的車要離開了"<<endl 
  <<"停車時(shí)間為： " 
  <<(h*60+m)-(parking.top().hour*60+parking.top().minute)<<"分鐘"<<endl 
  <<"停車費(fèi)用為：" 
  <<((h*60+m)-(parking.top().hour*60+parking.top().minute))*5<<"元"<<endl; 
   parking.pop(); 
  
  while(!cars.empty()) 
  { 
   parking.push(cars.top()); 
  cars.pop(); 
  } 
  
  while(parking.size()<MAX2) 
  { 
  if(waits.size()!=0) 
  { 
   for(int m=0;m<MAX2;m++) 
   { 
   if(z[m]==0) 
   { 
    z[num]=waits.front().number; 
   } 
   } 
   parking.push(waits.front());  
   waits.pop(); 
  } 
  else 
  { 
   break; 
  } 
 
  } 
 } 
  
 else 
 { 
  cout<<"沒有該輛車！請輸入正確的車牌號(hào)："<<endl; 
 }   
  
 } 
  
} 
 
void parkinglot() 
{ 
 r2: 
 cout<<endl<<"  **停車場管理程序**  "<<endl 
 <<"--------------------------------------------------"<<endl 
 <<"**" 
 <<"** A---汽車進(jìn)車場 D---汽車出車場 E---退出程序 **"<<endl 
 <<"--------------------------------------------------"<<endl 
 <<"請選擇：<A ,D ,E>:"; 
 char choose; 
 cin>>choose; 
 if(choose=='A' || choose=='D' || choose=='E') 
 { 
  switch(choose) 
  { 
  case 'A': 
   goIn(); 
   goto r2; 
  case 'D': 
   goOut(); 
   goto r2; 
  case 'E': 
   break; 
  } 
 } 
 else 
 { 
  cout<<"您的輸入有誤，請輸入 <A D E> 其中的一項(xiàng)。"; 
  goto r2; 
 } 
} 
 
int main() { 
 int i, j; 
 int iAA; 
 ALGraph *G=new ALGraph(); 
 int choose=0; 
 cout<<endl; 
 
 while(true) { 
r: 
 cout<<"------------------------------------------"<<endl 
  <<"  歡迎使用景區(qū)信息管理系統(tǒng) "<<endl 
  <<"  ***請選擇菜單***  "<<endl 
  <<"------------------------------------------"<<endl 
  <<" 1、創(chuàng)建景區(qū)景點(diǎn)分布圖   "<<endl 
  <<" 2、輸出景區(qū)景點(diǎn)分布圖   "<<endl 
  <<" 3、輸出導(dǎo)游線路圖   "<<endl 
  <<" 4、輸出導(dǎo)游線路圖的回路  "<<endl 
  <<" 5、查找及排序    "<<endl 
  <<" 6、求兩個(gè)景點(diǎn)間的最短路徑和最短距離 "<<endl 
  <<" 7、輸出道路修建規(guī)劃圖   "<<endl 
  <<" 8、停車場車輛進(jìn)出記錄信息  "<<endl 
  <<" 0、退出系統(tǒng)    "<<endl 
  <<"請輸入您要選擇的菜單項(xiàng): "; 
  
 cin>>choose; 
  
 if(choose<=8 && choose>=0) { 
  if(choose>1 && G->vexnum==0 &&choose!=8) { 
  cout<<endl<<"************您的圖為空，請先創(chuàng)建您的圖**********：" 
  <<endl<<endl; 
  goto r; 
  } else { 
  switch(choose) { 
 
   case 1: 
   CreateUDN(*G); 
 
   break; 
   case 2: 
   PrintAdjList(*G); 
   cout<<endl; 
   OutputGraph(*G); 
   break; 
   case 3: 
   cout<<"導(dǎo)游路線為："; 
   //CreatTourSortGraph(*G); 
   //DFSTraverse(*G); 
   break; 
   case 4: 
   JudgeCir(*G); 
   break; 
   case 5: 
    
   while(true) 
   { 
   int ch; 
   cout<<"您需要" 
    <<" 查找(0)，" 
    <<"按歡迎度排序(1)，" 
    <<"按景點(diǎn)岔路數(shù)排序(2)，" 
    <<"退出此目錄(3) :" ; 
   cin>>ch; 
   string sA; 
   switch(ch) 
   { 
    case 0: 
    cout<<"請輸入您要查找的有關(guān)景點(diǎn)的關(guān)鍵字：" ; 
    cin>>sA; 
    Search(*G,sA); 
    break; 
    case 1: 
    SortWel(*G); 
    break; 
    case 2: 
    SortN(*G); 
    break; 
    case 3: 
    goto r; 
    default : 
    cout<<"您的輸入有誤，請重新輸入："<<endl; 
   } 
   } 
   case 6: 
   printShortestPath(*G); 
   break; 
   case 7: 
   prim(*G,0,arr); 
   break; 
   case 8: 
   parkinglot(); 
   break; 
   case 0: 
   exit(0); 
  } 
 
  } 
  cout<<endl; 
 } 
 else { 
  cout<<"您的輸入有誤，請重新輸入0-8之間的數(shù)字"<<endl; 
 
 } 
 
 
 } 
 return 0; 
}