#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

typedef struct{
    char stop_name[17];
    int trans_time;
}Stop;
/*typedef struct EdgeT Edge;
struct EdgeT{
    char time[5];
    int which_route;
    int dest;
    Edge *next;
};
typedef struct EdgeT {
    char time[5];
    int which_route;
    int dest;
    struct EdgeT *next; // Note that you can use `struct EdgeT` instead of `Edge` here.
} Edge;
typedef struct GraphRep *Graph;
typedef struct{
    Edge **edges;
    int nV;
}GraphRep;
Graph newGraph(int V) {
    assert(V >= 0);
    int i;

    Graph g = malloc(sizeof(GraphRep));
    assert(g != NULL);
    g->nV = V;

    // allocate memory for each row
    g->edges = malloc(V * sizeof(Edge *));
    assert(g->edges != NULL);

    // initialize each row to NULL (no edges yet)
    for (i = 0; i < V; i++) {
        g->edges[i] = NULL;
    }

    return g;
}*/
typedef struct GraphRep *Graph;

// vertices are ints
//typedef int Vertex;

// edges are pairs of vertices (end-points)
typedef struct EdgeT {
    char time[5];
    int which_route;
    int dest;
    struct EdgeT *next; // Note that you can use `struct EdgeT` instead of `Edge` here.
} Edge;
typedef struct GraphRep {
    Edge  **edges;   // adjacency
    int    nV;      // #vertices
    int    nE;      // #edges
} GraphRep;

Graph newGraph(int V) {
    assert(V >= 0);
    int i;

    Graph g = malloc(sizeof(GraphRep));
    assert(g != NULL);
    g->nV = V;
    g->nE = 0;

    // allocate memory for each row
    g->edges = malloc(V * sizeof(int *));
    assert(g->edges != NULL);
    // allocate memory for each column and initialise with 0
    for (i = 0; i < V; i++) {
        g->edges[i] = calloc(V, sizeof(int));
        assert(g->edges[i] != NULL);
    }

    return g;
}
char time_before[5];
int find_index(Stop *stops,char *stop_name,int size_net){
    int i;
    for(i=0;i<size_net;i++){
        if(strcmp(stops[i].stop_name,stop_name)==0){
            return i;
        }
    }
    return -1;
}

time_t convert_time(char *t){
    char hour[3];
    char min[3];
    strncpy(hour, t, 2);
    strncpy(min, t + strlen(t) - 2, 2);
    struct tm timeStruct;
    time_t currentTime;
    time(&currentTime);
    struct tm *currentTimeInfo=localtime(&currentTime);
    timeStruct.tm_year=currentTimeInfo->tm_year;
    timeStruct.tm_mon=currentTimeInfo->tm_mon;
    timeStruct.tm_mday=currentTimeInfo->tm_mday;
    timeStruct.tm_hour=atoi(hour);
    timeStruct.tm_min=atoi(min);
    timeStruct.tm_sec=0;
    time_t timestamp=mktime(&timeStruct);
    return timestamp;
}
bool check_time(char *time1,char *time2){
    time_t t1= convert_time(time1);
    time_t t2= convert_time(time2);
    if(t1-t2<=0){
        return true;
    }
    return false;
}
time_t time_add(char *time,int min){
    time_t t=convert_time(time);
    time_t seconds=min*60;
    struct tm *timeInfo=localtime(&t);
    timeInfo->tm_sec+=seconds;
    time_t newT=mktime(timeInfo);
    return newT;
}
Edge *append(Edge *head,char *time,int which_route,int dest){
    Edge *e= malloc(sizeof(Edge));
    assert(e!=NULL);
    e->which_route=which_route;
    e->dest=dest;
    strcpy(e->time,time);
    e->next=NULL;
    if(head==NULL){
        head=e;
        return head;
    }
    Edge *curr=head, *prev=NULL;
    while(check_time(time,curr->time)){
        prev=curr;
        curr=curr->next;
        if(curr==NULL){
            break;
        }
    }
    prev->next=e;
    e->next=curr;
    return head;
    //e->next=head;
    //return e;
}
bool dfs_search(Graph g,int from,int to,int *visited,Edge *prev,Stop *stops){
    if(from==to){
        return true;
    }else{
        Edge *head=g->edges[from];
        while (head!=NULL){
            if(head->dest!=-1 && visited[head->dest]==-1 && check_time(head->time,time_before)){
                if(prev!=NULL && prev->which_route!=head->which_route){
                    int trans_time=stops[prev->dest].trans_time;
                    time_t new_time= time_add(head->time,trans_time);
                    time_t tb= convert_time(time_before);
                    if(new_time-tb<=0){
                        visited[head->dest]=from;
                        if(dfs_search(g,head->dest,to,visited,head,stops)){
                            return true;
                        }
                    }
                }else{
                    visited[head->dest]=from;
                    if(dfs_search(g,head->dest,to,visited,head,stops)) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
/*void print_path(int *visited,int from,int to){
    if(to==from){
        printf("to: %d\n",to);
        return;
    }
    print_path(visited,stops,from,visited[to]);
    printf("to: %d\n",to);
}*/
void print_path(int *visited, int from, int to, Stop *stops) {
    if (to == from) {
        printf("to: %s\n", stops[to].stop_name);
        return;
    }
    print_path(visited, from, visited[to], stops);
    printf("to: %s\n", stops[to].stop_name);
}

int main(int argc, char *argv[]) {
    printf("size of network: ");
    int size_net;
    scanf("%d", &size_net);
    Graph g=newGraph(size_net);
    Stop *stops=malloc(sizeof(stops) *size_net);
    assert(stops!=NULL);
    int i;
    char station_name[17];
    int transfer_time;
    for(i=0;i<size_net;i++){
        scanf("%s", &station_name);
        scanf("%d", &transfer_time);
        stops[i].trans_time=transfer_time;
        strcpy(stops[i].stop_name,station_name);
    }
    printf("Number of timetables: ");
    int num_tt;
    scanf("%d", &num_tt);
    int num_stop;
    char time[5];
    char stop_name[17];
    for(i=0;i<num_tt;i++){
        printf("Number of stops: ");
        scanf("%d", &num_stop);
        int j;
        char prev[17]="";
        for(j=0;j<num_stop;j++){
            scanf( "%s", &stop_name);
            if(strcmp(prev,"")!=0){
                int prev_index=find_index(stops,prev,size_net);
                int dest_index=find_index(stops,stop_name,size_net);
                g->edges[prev_index]=append(g->edges[prev_index],time,i,dest_index);
            }
            scanf("%s", &time);
            strcpy(prev,stop_name);
        }
        int stop_index=find_index(stops,prev,size_net);
        g->edges[stop_index]=append(g->edges[stop_index],time,i,-1);
    }
    char from[17];
    char to[17];
    //char time_before[5];
    while(1){
        printf("From: ");
        scanf("%s", &from);
        if(strcmp("done",from)==0 ){
            printf("Bye: ");
            break;
        }
        printf("To: ");
        scanf("%s", &to);
        printf("Arrive at or before: ");
        scanf("%s", &time_before);
        int from_index=find_index(stops,from,size_net);
        int to_index=find_index(stops,to,size_net);
        int *visited= malloc(sizeof(int)*size_net);
        assert(visited!=NULL);
        for(i=0;i<size_net;i++){
            visited[i]=-1;
        }
        visited[from_index]=from_index;
        bool res=dfs_search(g,from_index,to_index,visited,NULL,stops);
        if(res){
            //print_path();
            print_path(visited, from_index, visited[to_index], stops);
        }else{
            printf("No connection!\n");
        }
    }
    return 0;
}