:)

graphsearch.py

# -*- coding: utf-8 -*-

from collections import namedtuple

Vertex = namedtuple('Vertex', 'id, edges')
Edge = namedtuple('Edge', 'edge_from, edge_to, label, weight')


def load_graph(filename):
    with open(filename) as f:
        parse = lambda s: map(int, s.split())
        N, M, T, L = parse(f.readline())
        G = map(lambda n: Vertex(n, []), range(N))
        traces = parse(f.readline())
        for line in f:
            edge_from, edge_to, label, weight = parse(line)
            G[edge_from].edges.append(Edge(
                G[edge_from], G[edge_to], label, weight))
    return G, traces


def dfs_search(G, traces):
    fringe = zip(zip(G), [0] * len(G))
    best_path = best_cost = None
    while fringe:
        path, cost = fringe.pop()
        n = len(path) - 1
        if n == len(traces):
            if best_cost is None or cost < best_cost:
                best_path, best_cost = path, cost
            continue
        for e in path[-1].edges:
            if e.label != traces[n]:
                continue
            if best_cost is not None and cost + e.weight >= best_cost:
                continue
            fringe.insert(0, (path + (e.edge_to,), cost + e.weight))
    return best_cost, map(lambda v: v.id, best_path)

print dfs_search(*load_graph('input.txt'))