#!/usr/bin/python
# -*- coding: koi8-r -*-
import copy

class FindPath:
        def __init__(self, graph, delta):
                self.set_graph(graph)
                self.maxerror = delta  #number of minutes on which path can be longer
                                       #than shortest already found path

        def set_graph(self, graph):
                self.graph = graph
                self.helper = dict()
                for f in xrange(len(self.graph)):
                        for t in self.graph[f]:
                                if t[1] != 0:
                                        self.helper[(f, t[0])] = 1
                                        self.helper[(t[0], f)] = 1

        def __mj_rec__(self, num, target, path, jumps, pathjumps):
                path.append(num)
                if num == target:
                        self.PathList.append(copy.copy(path))
                        return -1
                for i in xrange(len(self.graph[num])):
                        if self.graph[num][i][0] not in path:
                                if self.graph[num][i][2] != self.graph[num][i][3]:
                                        if pathjumps + 1 > jumps:
                                                continue
                                        pathjumps += 1
                                ret = self.__mj_rec__(self.graph[num][i][0], target, path, jumps, pathjumps)
                                if self.graph[num][i][2] != self.graph[num][i][3]:
                                        pathjumps -= 1
                                path.pop()
                                if ret == -1:
                                        return 0
                return 0

        def minjumps(self, sfrom, sto, limit):
                self.PathList = list()
                jumps = 0
                while not len(self.PathList) and jumps < limit:
                        path = list()
                        self.__mj_rec__(sfrom, sto, path, jumps, 0)
                        jumps += 1
                return copy.copy(self.PathList)

        def waves_accurate(self, sfrom, sto, waitlenfunc):
                BIGNUM = 9999999
                maxerror = self.maxerror
                self.PathList = list()
                pl = list()        #array of pathes
                pll = list()       #array of "length" of pathes
                plj = list()       #array of jump/not jump flags
                minlens = [0] * len(self.graph)

                pl.append(list())
                pll.append(list())
                plj.append([0, 0])
                pl[0].append(sfrom)
                pll[0].append(waitlenfunc(sfrom))
                minlen = BIGNUM

                while len(pl):
                        nl = list()      #same as pl/pll/plj/pldict. for next iteration.
                        nll = list()
                        nlj = list()

                        #print len(pl)
                        for i in xrange(len(pl)):
                                if len(pl[i]):
                                        for s in self.graph[pl[i][-1]]:
                                                if s[1] == 0: #station is "under construction"?
                                                        continue
                                                curtime = pll[i][-1] + s[1]
                                                if s[0] == sto:
                                                        #path found, store it
                                                        jmp = 0
                                                        if s[2] != s[3]:
                                                                jmp = 1
                                                                if len(pl[i]) == 1 or plj[i][0]:
                                                                        curtime -= waitlenfunc(pl[i][-1])
                                                        minlen = min(minlen, curtime)
                                                        self.PathList.append([curtime, plj[i][1] + jmp] + pl[i] + [sto])
                                                elif not s[0] in pl[i] and (minlen == BIGNUM or curtime < minlen + maxerror):
                                                        app = 0
                                                        jmp = 0
                                                        if s[2] != s[3]:
                                                                #dont do useles jumps
                                                                if len(pl[i]) > 1 and self.helper.has_key((s[0], pl[i][-2])):
                                                                                continue
                                                                if len(pl[i]) == 1 or plj[i][0]:
                                                                        curtime -= waitlenfunc(pl[i][-1])
                                                                app = waitlenfunc(s[0])
                                                                jmp = 1
                                                        if minlens[s[0]] == 0 or minlens[s[0]] + maxerror > curtime:
                                                                curtime = curtime + app
                                                                nl.append(pl[i] + [s[0]])
                                                                nll.append(pll[i] + [curtime])
                                                                nlj.append([jmp, plj[i][1] + jmp])
                                                                if minlens[s[0]] == 0 or minlens[s[0]] > curtime:
                                                                        minlens[s[0]] = curtime

                        pl = nl
                        pll = nll
                        plj = nlj

                return copy.copy(self.PathList)

        def waves(self, sfrom, sto, waitlenfunc):
                self.PathList = list()
                pl = list()
                pl.append(list())
                pl[0].append(waitlenfunc(sfrom))
                pl[0].append(sfrom)
                minlen = -1

                while len(pl):
                        nl = list()
                        for l in pl:
                                for s in self.graph[l[-1]]:
                                        if s[0] == sto:
                                                fp = l[1:] + [sto]
                                                self.PathList.append(fp)
                                                fpl = l[0] + s[1]
                                                if minlen == -1 or fpl < minlen:
                                                        minlen = fpl
                                        #there is one error - station should be
                                        #dropped only if previous found path is shorter
                                        #then current path _in seconds_, not in "hops".
                                        #thats done in waves_accurate, which is slower than
                                        #this function
                                        elif minlen == -1 or l[0] < minlen:
                                                if not filter(lambda a: a, map(lambda a: s[0] in a[1:], pl)):
                                                        app = 0
                                                        if s[2] != s[3]:
                                                                app = waitlenfunc(s[0])
                                                        nl.append([l[0] + s[1] + app] + l[1:] + [s[0]])
                        pl = nl

                return copy.copy(self.PathList)