= paths =
== 問題 ==
There are many paths, and search for shortest path from start to goal.

{{{
(to, cost)
}}}

== メモ ==

== 解法 ==
Dijkstra法を書くだけ。
{{{#!highlight python
from Queue import PriorityQueue
def dijkstra(start):
    back = list()
    cost = list()
    for i in range(len(E)):
        back.append(None)
        cost.append(None)
    q = PriorityQueue()
    q.put((0, start))
    while not q.empty():
        p = q.get()
        src = p[1]
        for e in E[src]:
            dst = e[0]
            c = p[0] + e[1]
            if cost[dst] is not None and cost[dst] <= c:
                continue
            back[dst] = src
            cost[dst] = p[0] + e[1]
            q.put((cost[dst], dst))
    return (back, cost)
def shortest_path(start, goal, back, cost):
    route = []
    p = goal
    while p != start:
        route.append(p)
        p = back[p]
    route.reverse()
    return route
sys.argv[1:] = shortest_path(start, goal, *dijkstra(start))
}}}

{{{
the flag is: ADCTF_G0_go_5hOr7E57_PaTh
}}}