/*TRAFFIC.H*/
#define MAX_VERTEX_NUM 50
#define MAX_PATH 100
#define MAX_LINE 50
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define YES 1
#define NO 0
#define OVERFLOW -2
#define MAXERROR 3
#define MAXVER 16
#define MAX 32767
#define NEXTSTEP getch()

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<conio.h>   


typedef int status;
typedef char step;
typedef char CityName[MAXVER];
typedef int StrARR[MAX_PATH][MAX_VERTEX_NUM+1];   

typedef struct Dtime
{
int hour;
int minute;
}Dtime;

typedef struct Tooltype
{
int money;
int line;
struct Dtime starttime[MAX_LINE];
struct Dtime drivetime;
}Tooltype;

typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
Tooltype * Tool[2];    /* 分別指向火車和飛機*/
}ArcNode;

typedef struct VNode
{
CityName data;
ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;

void openfile(char *);
step Scanall(ALGraph G);
step Scandes(ALGraph G);
step Scanstart(ALGraph G);
int LocateVex(ALGraph G,CityName v);
step Edit(ALGraph &G);
void editsucc(ALGraph G);
step Exit();
status DestroyGraph(ALGraph &G);
status Inite(ALGraph &G);
status Save(ALGraph G);
status Creat(ALGraph &G);
step Scan(ALGraph G);
step Addarc(ALGraph &G);
step Delarc(ALGraph &G);
step Addvex(ALGraph &G);
step Delvex(ALGraph &G);
step Inqurie(ALGraph G);
status GLtime(Dtime a,Dtime b);
void AllPath(ALGraph , int from, int to,StrARR , int &i);
step Shorttime(ALGraph ,int tool,StrARR path,int n);
step Lessmoney(ALGraph ,int tool,StrARR path,int n);
step Lesschange(ALGraph ,int tool,StrARR path,int n);
void Counttime(Dtime &arrive,Dtime start,Dtime drive,int & day ,int &hour,int &minute);
void DFS(ALGraph G,int i);
status DFSTraverse(ALGraph G);
void printpath(ALGraph G,int kind,StrARR path,int min);

/*MAIN.CPP*/
status visited[MAX_VERTEX_NUM];
void main()
{
 char c = '0';
 ALGraph G;
 textbackground(1);
 textcolor(7);
 openfile("name");
 getch();
 Inite(G);
while(c != 'y')
{
 if(c == '0')
  {
  openfile("main");
  c = NEXTSTEP;
  }
 switch(c)
  {
  case '1':case 's':case 'S':
  c = Scan(G);break;
  case '2':case 'e':case 'E':
  c = Edit(G);break;
  case '3':case 'i':case 'I':
  c = Inqurie(G);break;
  case '4':case 'q':case 'Q':
  c = Exit();break;
  default:c = '0';
  }
}
openfile("Bye");
getch();
}

/*Addarc.CPP*/
step Addarc(ALGraph &G)
 {
   CityName from,to;
   int hour,minute,i = -1,j = -1,k,error = 0;
   Dtime leave;
   ArcNode *p;
   openfile("head");
   while( i == -1)
    {                       /*input   the  starte station*/
      printf("please input the addarc leave station.\n");
      scanf("%s",from);
      i = LocateVex(G,from);
      if(i == -1)
      {
        printf("There is no %s station\n",from);
	    error ++;
	    if(error == MAXERROR)   /*too many  error times*/
	    {                 
	      openfile("error");
           return NEXTSTEP;
	    }
        printf("please reinput:");
      }
    }
    
    error = 0;
   while( j == -1)
    {                    /*input  the terminus station*/
      printf("please input the addarc terminus station.\n");
      scanf("%s",to);
      j = LocateVex(G,to);
      if(j == -1)
      {
	    printf("There is no %s station\n",to);
	    error ++;
	    if(error == MAXERROR)
	    {
	      openfile("error");
           return NEXTSTEP;
	    }
	     printf("please reinput:");
      }
    }
    
    for(p = G.vertices[i].firstarc; p && p -> adjvex !=j;p = p -> nextarc);  /*search  the  arc  from i  to  j*/
    if(!p)                                                                   /*if not  exist  creat  the  arc*/
      {   
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p -> adjvex = j;
        p -> nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
	    p -> Tool[0] = NULL;
	    p -> Tool[1] = NULL;
      }
      
      i = -1;
      error = 0;
   while(i == -1)
   {
    printf("Which vehicle do you want to add?\n    1 train \n    2 fly\n");
    scanf("%d",&i);
    getchar();
    if(i != 1&&i != 2)  /*input  error!*/ 
    {
      error ++;
     if(error == MAXERROR)
	    {
	      openfile("error");
           return NEXTSTEP;
	    }
      printf("input error!please reinput!\n");
      i = -1;
    }

    else 
     {
       if(!p -> Tool[i-1])
        {                                            /*the  first  arc  , add   the arc infomation*/
         printf("This is the first line\n");
	     p -> Tool[i-1] = (Tooltype *)malloc(sizeof(Tooltype));
	 printf("How much money drive to %s by this tool\n",to);
	     scanf("%d",&p-> Tool[i-1] ->money);
	     printf("How long drive for %s to %s?(hour:minute)\n",from,to);
	     scanf("%d:%d",&p -> Tool[i-1] -> drivetime .hour,& p -> Tool[i-1] -> drivetime .minute);
	     p -> Tool[i-1] -> line = 0;
        }
         printf("please input the leave time.(hour:minute)\n");
         scanf("%d:%d",&leave.hour,&leave.minute);
         if(p -> Tool[i-1] ->line == MAX_LINE)
          {               /*the   line  is  Full*/
            openfile("head");
	        printf("The line  if  FULL!!\nCan not add other arc!\n");
	      }
	  else
	   {
	   for(k = 0;(k < p -> Tool[i-1] -> line)&& GLtime(leave,p->Tool[i-1]->starttime[k]);k ++);
	   if(leave.hour == p->Tool[i-1]->starttime[k].hour &&
	      leave.minute == p -> Tool[i-1]->starttime[k].minute)
	    {
	      openfile("head");
	      printf("This line is exist!!\n");
	      return NEXTSTEP;
	    }
	 for(j = p -> Tool[i-1] -> line;j > k;j --)
	 {
	  p->Tool[i-1]->starttime[j].hour = p->Tool[i-1]->starttime[j-1].hour;
	  p->Tool[i-1]->starttime[j].minute = p->Tool[i-1]->starttime[j-1].minute;
         }
          p->Tool[i-1]->starttime[k].hour = leave.hour;
	  p->Tool[i-1]->starttime[k].minute = leave.minute;
	  p -> Tool[i-1] -> line ++;
	   openfile("head");
       printf("add success!\n");
      }
     }
  }
   return NEXTSTEP;
 }
 
 /*Addvex.CPP*/
 step Addvex(ALGraph &G)
 {
   CityName add;
   openfile("head");
   if(G.vexnum == MAX_VERTEX_NUM)
    {
     printf("Full !!\n");
     return NEXTSTEP;
    }
   printf("Please input the station name:\n");
   scanf("%s",add);
   getchar();
   if(LocateVex(G,add) != -1)
   {
    printf("The station is exist!!");
    }
    else 
    {
     strcpy(G.vertices[G.vexnum].data,add);
     G.vertices[G.vexnum].firstarc = NULL;
     G.vexnum ++;
     printf("%s station add success!!\n",add);
    }
  return NEXTSTEP;
 }
 
 /**/void AllPath(ALGraph g, int from, int to,StrARR path, int &i)
{
int m,j;
ArcNode *p;
extern visited[];

for(m = 0 ; path[i][m]!=-1 ;m++); /* Add "from" to the path*/
path[i][m] = from;

visited[from] = TRUE;
if(from == to)  /*search  the  line*/
{ 
i++;
for(m = 0;path[i-1][m]!=-1;m++)
path[i][m] = path[i-1][m];
}
else
 for(p = g.vertices[from].firstarc;p;p = p->nextarc)
  {         /*DFS trave*/
    if(!visited[p->adjvex])
    AllPath(g,p->adjvex,to,path,i);
  }
  
visited[from] = FALSE;

for(m = 0; path[i][m] != from && path[i][m]!=-1; m++);  /*delete "from" from the path*/
path[i][m] = -1;
}

/**/
void Counttime(Dtime &arrive,Dtime start,Dtime drive,int & day ,int &hour,int &minute)
  /*arrive  at arrivetime  start at start time  ,drive in the  way pay  the drive time*/
  /*count  the  total time  and  return it  by  day,hour,minute*/
 { 
   minute = minute + drive.minute + start.minute - arrive.minute;
   if(minute < 0)
    {
      hour --;
      minute += 60;
    }
   else if(minute >= 60)
    {
     hour ++;
     minute -=60;
    }
  hour = hour + drive.hour + start.hour - arrive.hour;
    if( hour < 0)
    {
      day --;
      hour +=24;
    }
    else if(hour >= 24)
     {
       day = day + hour/24;
       hour = hour%24;
     }
   arrive.minute = start.minute + drive.minute;
    if(arrive.minute >= 60)
     {
       arrive.hour = 1;
       arrive.minute=arrive.minute%60;
       arrive.hour = start.hour + drive.hour + 1;
     }
   else 
   arrive.hour = start.hour + drive.hour;
   if(arrive.hour>=24)
    arrive.hour = arrive.hour%24;
 }
 
 /**/
 void Counttime(Dtime &arrive,Dtime start,Dtime drive,int & day ,int &hour,int &minute)
  /*arrive  at arrivetime  start at start time  ,drive in the  way pay  the drive time*/
  /*count  the  total time  and  return it  by  day,hour,minute*/
 { 
   minute = minute + drive.minute + start.minute - arrive.minute;
   if(minute < 0)
    {
      hour --;
      minute += 60;
    }
   else if(minute >= 60)
    {
     hour ++;
     minute -=60;
    }
  hour = hour + drive.hour + start.hour - arrive.hour;
    if( hour < 0)
    {
      day --;
      hour +=24;
    }
    else if(hour >= 24)
     {
       day = day + hour/24;
       hour = hour%24;
     }
   arrive.minute = start.minute + drive.minute;
    if(arrive.minute >= 60)
     {
       arrive.hour = 1;
       arrive.minute=arrive.minute%60;
       arrive.hour = start.hour + drive.hour + 1;
     }
   else 
   arrive.hour = start.hour + drive.hour;
   if(arrive.hour>=24)
    arrive.hour = arrive.hour%24;
 }
 
 /**/
 step Delvex(ALGraph &G)
  {
  int v = -1,error,delarc = 0,i;
  CityName station;
  ArcNode *p,*q;
  openfile("head");
 while(v == -1)
 { 
  printf("which station do you want to delete?\n");
  scanf("%s",station);
  getchar();
  v = LocateVex(G,station);
  if( v == -1)
  {
   printf("There is no %s station\n",station);
    error++;
    if(error == MAXERROR)
     {
       openfile("error");
       return NEXTSTEP;
     }
  }
 }
 
   delarc = 0;
   for(i = 0;i < G.vexnum; i++)
   {
   if(i == v)
    continue;
    p = G.vertices[i].firstarc;
    while(p)
    {
     if(p->adjvex>v)
      p->adjvex--;
     else if(p -> adjvex == v)
     {
      if(p == G.vertices[i].firstarc)
        {
        G.vertices[i].firstarc = p -> nextarc;
        if(p -> Tool[0])
          {
           free(p -> Tool[0]);
	       p->Tool[0] = NULL;
          }
        if(p -> Tool[1])
          {
           free(p -> Tool[1]);
           p->Tool[1] = NULL;
          }
	    free(p);
	    p =  G.vertices[i].firstarc;
        delarc ++;
        }//if(p == G.vertices[i].firstarc)
       
      else
       {
         q -> nextarc = p -> nextarc;
         if(p -> Tool[0])
         {
          free(p -> Tool[0]);
          p->Tool[0] = NULL;
         }
         if(p -> Tool[1])
          {
          free(p -> Tool[1]);
          p->Tool[1] = NULL;
          }
         free(p);
         delarc ++;
         p = q -> nextarc;
       }
     }//if(p -> adjvex == v)
     else 
     {
      q = p;
      p = p -> nextarc;
     }
    }// while(p) 
   }// for(i = 0;i < G.vexnum; i++)
   
   for(p = G.vertices[v].firstarc;p;) /*delete the arc of from v*/
    {
     q = p;
     p = p -> nextarc;
     if(q -> Tool[0])
      {
       free(q -> Tool[0]);
       q ->Tool[0] = NULL;
      }
     if(q -> Tool[1])
      {
      free(q -> Tool[1]);
      q ->Tool[1] = NULL;
      }
     free(q); 
     delarc ++;
    }
    
   G.vertices[v].firstarc = NULL;
   for( i = v;i < G.vexnum-1; ++i)   
   {
      strcpy(G.vertices[i].data,G.vertices[i+1].data);
      G.vertices[i].firstarc = G.vertices[i+1].firstarc;
   }
   G.vertices[i].firstarc = NULL;
   G.vexnum--;
   G.arcnum -= delarc;
   printf("delet success!!\n") ;
   return NEXTSTEP;
  }
  
  /**/
  void DFS(ALGraph G,int i)
 {
   ArcNode *p;
    extern visited[];
   visited[i] = TRUE;
   printf("%10s to:  ",G.vertices[i].data);
  for(p = G.vertices[i].firstarc; p ;p = p -> nextarc)
  printf("%10s",G.vertices[p -> adjvex].data);
  printf("\n");
  for(p = G.vertices[i].firstarc;p ; p = p -> nextarc)
   if(!visited[p ->adjvex])
    DFS(G,p->adjvex);
 }
 
status DFSTraverse(ALGraph G)
{
 int i;
 extern visited[];
 for(i = 0;i < G.vexnum;++i)
   visited[i] = FALSE;
 for(i = 0;i < G.vexnum;++i)
  if(!visited[i])
    DFS(G,i);
return OK;
}

/**/
step Edit(ALGraph &G)
 {
   step c = '0';
 while(c == '0')
 {
   openfile("edit");
   c = NEXTSTEP;
   switch(c)
   {
     case '1':
     c = Addarc(G);break;
     case '2':
     c = Delarc(G);break;
     case '3':
     c = Addvex(G);break;
     case '4':
     c = Delvex(G);break;
     case 's':case 'i':case 'q':case 'e':
     case 'S':case 'I':case 'Q':case 'E':
     break;
     default:c='0';
   }
 }
return c;
}

/**/
step Exit()
 {
    openfile("exit");
    return NEXTSTEP;
 }