＃ 第一题应该是dijkstra's algorithm的变种？没来得及仔细debug，通过率0%。第二题看起来简单，到交卷了才发现编号只能0-9，通过率0% （此处应该微笑

def minTravelTime(intersections, roads, start, goal):
    frontier = []
    frontier.append([start, 0])
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0
    t = 0

    while len(frontier) > 0:
       current = min(frontier, key=lambda x: x[1])
       frontier.remove(current)
       current = current[0]

       if current == goal:
          print(current)
          return cost_so_far(current)

       for next in get_neighbors(current, roads):
          wait_time = get_wait_time(next[0], intersections, t)
          new_cost = cost_so_far[current] + wait_time + next[2]
          t = t + wait_time + next[2]
          if next[1] not in cost_so_far or new_cost < cost_so_far[next[1]]:
             cost_so_far[next[1]] = new_cost
             frontier.append([next[1], new_cost])
             came_from[next] = current

def get_neighbors(node, roads):
    results = []
    for road in roads:
        if node == roads[0]:
            results.append(road)
    return results

def get_wait_time(node, intersection, t):
    change = intersection[node]
    if (t/change)%2 == 0:
        return 0
    else:
        return ((t/change)+1)*change - t