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

typedef struct {
        int stn;
        double time;
        int linef;
        int linet;
} grel;

typedef struct {
        double dday;
        double dnight;
} delays_t;

grel **graph = NULL;
delays_t *delays = NULL;

#define fget_test(f, buf, size, graph, delays) \
        if(!fgets(buf, size, f)) { \
                fclose(f); \
                if(graph) { \
                        int ti; \
                        for(ti = 0; graph[ti]; ti++) \
                                free(graph[ti]); \
                        free(graph); \
                } \
                if(delays) \
                        free(delays); \
                return 0; \
        }

int load_data(void) {
//        FILE *f = fopen("graphtest.txt", "r");
        FILE *f = fopen("graphtest_london.txt", "r");
        char buf[256] = "\0";
        int nstat, nneigh, nlines, i, j;

        if(f == NULL)
                return 0;

        fget_test(f, buf, 256, graph, delays);
        nstat = atoi(buf);
        graph = calloc(nstat + 1, sizeof(grel *));

        for(i = 0; i < nstat; i++) {
        	fget_test(f, buf, 256, graph, delays);
                nneigh = atoi(buf);
                graph[i] = malloc((nneigh + 1) * sizeof(grel));
                graph[i][nneigh].stn = -1;
                for(j = 0; j < nneigh; j++) {
        		fget_test(f, buf, 256, graph, delays);
                        graph[i][j].stn = atoi(buf);

        		fget_test(f, buf, 256, graph, delays);
                        graph[i][j].time = atof(buf);

        		fget_test(f, buf, 256, graph, delays);
                        graph[i][j].linef = atoi(buf);

        		fget_test(f, buf, 256, graph, delays);
                        graph[i][j].linet = atoi(buf);
                }
        }

        fget_test(f, buf, 256, graph, delays);
        nlines = atoi(buf);
        delays = calloc(nlines + 1, sizeof(delays_t));
        for(i = 0; i < nlines; i++) {
        	fget_test(f, buf, 256, graph, delays);
                j = atoi(buf) - 1;
                if(j >= nlines || j < 0) {
                        printf("invalid line %d\n", j);
        		fget_test(f, buf, 256, graph, delays);
        		fget_test(f, buf, 256, graph, delays);
                } else {
        		fget_test(f, buf, 256, graph, delays);
	                delays[j].dday = atof(buf);
        		fget_test(f, buf, 256, graph, delays);
                	delays[j].dnight = atof(buf);
                }
        }

        fclose(f);
        return 1;
}

void find_path(int from, int to) {
        int **pathlist = NULL, **npathlist = NULL;
        double **pathlistl = NULL, **npathlistl = NULL, mintime = 999999, ntime;
        char *pathlistj = NULL, *npathlistj = NULL;
	int i, j, k, ns, npls, add, plnum;
        int MAXERR = 5;
        int *minlens;
        int ti;

        //printf("%d %d\n", from, to);
        for(i = 0; graph[i]; i++);
        minlens = calloc(i, sizeof(int));

        pathlist = calloc(2, sizeof(int *));
        pathlist[0] = malloc(2 * sizeof(int));
        pathlist[0][0] = 1;
        pathlist[0][1] = from;

        pathlistl = malloc(sizeof(double *));
        pathlistl[0] = malloc(sizeof(double));
        pathlistl[0][0] = delays[graph[from][0].linef].dday;

        pathlistj = malloc(sizeof(char));
        pathlistj[0] = 0;

        while(pathlist && pathlist[0]) {
                npls = 0;
                for(i = 0; pathlist[i]; i++) {
                        plnum = pathlist[i][0];
                        ns = pathlist[i][plnum];
                        for(j = 0; graph[ns][j].stn != -1; j++) {
                        	ntime = pathlistl[i][plnum - 1] + graph[ns][j].time;
                                if(graph[ns][j].linef != graph[ns][j].linet) {
                                        if(plnum == 1) {
                                                ntime -= delays[graph[ns][j].linef].dday;
                                        } else if(plnum > 1 && pathlistj[i]) {
                                                continue;
                                        }
        				ntime += delays[graph[ns][j].linet].dday;
                                }

                                if(mintime != 999999 && mintime + MAXERR < ntime)
                                        continue;
                                if(graph[ns][j].stn == to) {
                                        if(mintime == 999999 || mintime > ntime)
                                        	mintime = ntime;
                                        //for(ti = 0; ti < pathlist[i][0]; ti++)
                                        //       printf("%d ", pathlist[i][ti + 1]);
                                        //printf("%d (%f)\n", to, ntime);
                                        continue;
                                }

                                if(minlens[graph[ns][j].stn] != 0 && minlens[graph[ns][j].stn] + MAXERR < ntime)
                                	continue;

                                add = 1;
                                for(k = 0; k < pathlist[i][0]; k++)
                                	if(graph[ns][j].stn == pathlist[i][k + 1]) {
                                                add = 0;
                                                break;
                                        }

                                if(add) {
	                                npls++;
        	                        npathlist = realloc(npathlist, (npls + 1) * sizeof(int *));
        	                        npathlist[npls - 1] = malloc((plnum + 2) * sizeof(int));
                	                memcpy(npathlist[npls - 1], pathlist[i], (plnum + 1) * sizeof(int));
                                	npathlist[npls - 1][0] = plnum + 1;
                                	npathlist[npls - 1][plnum + 1] = graph[ns][j].stn;
	                                npathlist[npls] = NULL;

        	                        npathlistl = realloc(npathlistl, npls * sizeof(double *));
        	                        npathlistl[npls - 1] = malloc((plnum + 1) * sizeof(double));
                	                memcpy(npathlistl[npls - 1], pathlistl[i], plnum * sizeof(double));
                                        npathlistl[npls - 1][plnum] = ntime;

        	                        npathlistj = realloc(npathlistj, npls * sizeof(char));
                                        npathlistj[npls - 1] = graph[ns][j].linef != graph[ns][j].linet ? 1 : 0;

                                        if(minlens[graph[ns][j].stn] == 0 || minlens[graph[ns][j].stn] > ntime)
                                                minlens[graph[ns][j].stn] = ntime;
                                }
                        }
                        free(pathlist[i]);
                        free(pathlistl[i]);
                }
                free(pathlist);
                pathlist = npathlist;
                npathlist = NULL;
                free(pathlistl);
                pathlistl = npathlistl;
                npathlistl = NULL;
                free(pathlistj);
                pathlistj = npathlistj;
                npathlistj = NULL;
                //printf("npls - %d\n", npls);
        }

        if(pathlist)
        	free(pathlist);
}

int main(int argc, char **argv) {
        int i, j;

	if(!load_data()) {
                printf("data load error\n");
                return -1;
        }

        //find_path(0, 26);
        for(i = 0; graph[i]; i++) {
                printf("%d\n", i);
	        for(j = 0; graph[j]; j++)
                        if(i != j)
                                find_path(i, j);
        }

        return 0;
}