#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
#define PR printf
#define SIZE 10
#define MAXSIZE 25
#define maxint 32767
typedef int status;

typedef struct time_train{
	int day;
	int hour;
	int minute;
}time_train;
typedef struct town{
	char name[9];
	time_train arrive;
	time_train leave;
	struct town *next_town;
}town;
typedef struct train{
	char train_num[8];
	char start_place[9];
	char end_place[9];
	int fare;
	int hour;
	struct train *next_train;
	struct town *next_town;
}train;

typedef struct{
	int length;//長度
//	int hour;//時間
//	int fare;//費用
	int ivex,jvex;//
}path,*path_p;
typedef struct path_node{
	path pa;//
	struct path_node *i_link,*j_link;
}path_node,*path_node_p;
 
typedef struct {
	char city_name[9];
	path_node_p firsh_path;
}city_node,*city_p;

typedef struct {
	city_node adj_list[MAXSIZE];
	int city_num,path_num;
}graph_country;

typedef struct {
	int vx,vy;
}Edge;

typedef struct {
	Edge path[100];//路徑中邊的序列
	int len;//路徑中邊的數目
}path_city;

typedef struct {
	char citys[MAXSIZE][9];//路徑中城市的序列
	int num;
}p_city;//


train *init_train();//初始化鏈表
town *init_town();
status insert_train(train *l, char *train_num,char *start_place,char *end_place,int fare,int hour);
status find_train_num(train *l,char *train_num);
status find_place(train *l,char *start_place,char *end_place,char choice);
status creat_train(train *l);
status print_train(train *l);
status insert_town(train *l, char *name,time_train arrive,time_train leave);

status insert_path(graph_country *l,path pa);
status insert_city(graph_country *l,char *city_name,int i);
status init_graph(graph_country *l);
status creat_graph(graph_country *l);
void get_city(graph_country l,int i, char *city_name);
//以city_name返回鄰接多重表中序號為i頂點的城市名
path_node *first_path(graph_country l,int vi);
//返回圖中依附于頂點的第一條這的指針:l.adj_list [vi].firsh_path
path_node * next_path(graph_country g,int vi,path_node p,int *vj,path_node *q);
//以vj返回圖g中依附于頂點vi的一條邊(由指針p所指)的另一端點;
//以q返回圖中依附于頂點vi且相對于指針p所指邊的下一條邊


void init_p(path_city *pa);
//初始化為一條空路徑
void init_set(p_city *p);
void copy_path(path_city *pa1,path_city *pa2);
//復制路徑
void insert_p(path_city *pa,int v,int w);
//在pa中插入一條邊(v,w)
int path_length(path_city *pa);
//返回路徑長度
void out_path(graph_country l,path_city pa,p_city *citys);
//將路徑轉換為城市名稱的序列
void putin_set(char *city_name,p_city *p,int st);

void shortest_path(graph_country g,int st,int nd,int *pathlength,p_city *path_info);
//利用迪杰斯特拉算法的基本思想求圖g中從頂點st到頂點nd的一條最短路徑
//最短路徑path_info及其路徑長度path_lenth
int minnal(int *dist,p_city ss);
//求dist[]中的最小邊