Problem:


Problem C: Brave Princess Revisited

ある貧乏な国のおてんばで勇敢なお姫様が，政略結婚のため別の国に嫁ぐことになった．ところがお姫様を亡き者としようとしている悪漢が嫁ぎ先への道の途中で刺客を放っている．

お姫様を無事に相手国に送り届けるため，あなたは安全な経路を既に決定していたのだが，お姫様の今までに通ったことのない道を通ってみたいというわがままなたっての願いで別の道を通ることとなった．そこであなたは地図を見ながらお姫様が通る道を決めなおすことにした．

全ての道は，宿場同士をつなぐ街道である．便宜上，出発地点及び目的地点も宿場とする．ところが，新しい道は治安の問題を抱えていた．盗賊やお姫様を亡き者にしようとする刺客が襲いかかってくる可能性が高いのである．

そのような危険な道を通るには護衛を雇うことが望ましい．護衛は宿場で雇うことができ，道単位で姫を守らせることができる．護衛が守っている間は盗賊や刺客に襲われることはないが，距離 1 につき金 1 がかかる．そのため，護衛を雇うためには所持金よりも次の宿場までの距離が長くないことが条件となる．

いま，与えられた予算 L のもとで，姫が無事に目的地に着くまでに襲いかかってくる盗賊や刺客の人数を最小化することを考える．あなたの仕事は，その最小化された人数を求めることである．なお，宿場にいる間に襲われることはないものとする．

Input

入力は複数のデータセットからなる．各データセットは次の形式をしている．

N M L

A1 B1 D1 E1

A2 B2 D2 E2

...

AM BM DM EM

最初の行には 3 つの非負の整数 N (2 ≤ N ≤ 100)，M， L (0 ≤ L ≤ 100) が与えられる．これらの整数は，宿場の数，道の数，護衛を雇うための予算を表す．宿場には 1 から N までの番号が割り振られており，出発地には 1 ，目的地には N の番号がそれぞれ割り振られている．

続く M 行では道の情報が各行に 1 つずつ与えられる．道の情報は 4 つの整数 Ai，Bi (1 ≤ Ai < Bi ≤ N)， Di (1 ≤ Di ≤ 100) Ei (0 ≤ Ei ≤ 10000) で与えられる．これらはそれぞれ，道の始点と終点の宿場の番号，道の距離，盗賊や刺客に襲われる人数を表す．

道は双方向に通行可能であり，かつある宿場の組に対しては高々 1 つの道しか存在しない．また，出発地から目的地には必ず移動可能であることが保証されている．

入力の終わりは，空白で区切られた 3 つの 0 を含む 1 行で示される．

Output

各データセットについて，盗賊や刺客に襲われる人数の最小値を各行に出力せよ．出力に余計な空白や改行を含めてはならない．

Sample Input

3 2 10
1 2 8 6
2 3 10 3
3 2 10
1 2 3 8
2 3 7 7
3 3 10
1 3 17 6
1 2 2 4
2 3 9 13
4 4 5
1 3 9 3
1 4 7 25
2 3 8 2
2 4 9 3
0 0 0

Output for the Sample Input

3
0
4
8



Sample input:
3 2 10
1 2 8 6
2 3 10 3
3 2 10
1 2 3 8
2 3 7 7
3 3 10
1 3 17 6
1 2 2 4
2 3 9 13
4 4 5
1 3 9 3
1 4 7 25
2 3 8 2
2 4 9 3
0 0 0


Sample output:
3
0
4
8

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

INF = 10 ** 20

while True:
  n, m, l = map(int, input().split())
  if n == 0:
    break
  edges = [[] for _ in range(n * (l + 1))]
  for _ in range(m):
    a, b, d, e = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(d, l + 1):
      edges[i * n + a].append((0, (i - d) * n + b))
      edges[i * n + b].append((0, (i - d) * n + a))
    for i in range(l + 1):
      edges[i * n + a].append((e, i * n + b))
      edges[i * n + b].append((e, i * n + a))
  
  que = []
  heappush(que, (0, l * n))
  costs = [INF] * (n * (l + 1))
  costs[l * n] = 0
  while que:
    total, node = heappop(que)
    for enemy, to in edges[node]:
      if costs[to] > total + enemy:
        costs[to] = total + enemy
        heappush(que, (total + enemy, to))

  ans = min(costs[i * n + n - 1] for i in range(l + 1))
  print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    def f(n,m,l):
        e = collections.defaultdict(list)
        for _ in range(m):
            a,b,x,y = LI()
            e[a].append((b,x,y))
            e[b].append((a,x,y))

        d = collections.defaultdict(lambda: inf)
        d[(1, 0)] = 0
        q = []
        heapq.heappush(q, (0, 0, 1))
        v = collections.defaultdict(bool)
        mi = inf
        while len(q):
            c, k, u = heapq.heappop(q)
            if v[(u,k)]:
                continue
            v[(u,k)] = True
            if u == n and mi > c:
                mi = c

            for uv, ud, ue in e[u]:
                vk = k + ud
                vv = (uv, vk)
                if not v[vv] and vk <= l:
                    vd = c
                    if d[vv] > vd:
                        d[vv] = vd
                        heapq.heappush(q, (vd, vk, uv))
                vv = (uv, k)
                if not v[vv]:
                    vd = c + ue
                    if d[vv] > vd:
                        d[vv] = vd
                        heapq.heappush(q, (vd, k, uv))


        return mi

    while True:
        n,m,l = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m,l))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

while True:
    N, M, L = map(int, input().split())
    if N==M==L==0:
        break
    E = defaultdict(lambda: defaultdict(lambda: float("inf")))
    for _ in range(M):
        A, B, D, E_ = map(int, input().split())
        E[A][B] = (D, E_)  # 金、コスト
        E[B][A] = (D, E_)  # 金、コスト

    start = (1, 0)

    dist = defaultdict(lambda: float("inf"))  # 始点から各頂点までの(仮の)最短距離を格納する
    dist[start] = 0
    q = []  # 各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    heapq.heappush(q, (0, start))  # 始点をpush
    while len(q) != 0:
        prov_cost, v_m = heapq.heappop(q)  # pop  # 一度取り出された時点でコストは確定
        v, m_v = v_m

        # プライオリティキューに格納されている最短距離が
        # 現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[v] < prov_cost:
            continue

        if v==N:
            print(prov_cost)
            break

        # 辺を探索
        Us = {}
        for u, (m, c) in E[v].items():
            Us[(u, m_v)] = c
            if m_v+m <= L:
                Us[(u, m_v+m)] = 0

        for u_m, c in Us.items():
            if dist[u_m] > dist[v_m] + c:
                dist[u_m] = dist[v_m] + c  # distの更新
                heapq.heappush(q, (dist[u_m], u_m))  # キューに新たな仮の距離の情報をpush

Submission status: Accepted

Solution code:
import heapq
while True:
  n,m,l=map(int,raw_input().split())
  if n==0: break
  v={}
  for i in xrange(n):
    v[i] = []                                                                                                                                    # count attacked
  cost=[[10**9]*(l+1) for _ in xrange(n)]
  cost[0][l] = 0
  for _ in xrange(m):
    a,b,d,e=map(int,raw_input().split())
    a-=1
    b-=1
    v[a].append((b,d,e))
    v[b].append((a,d,e))
  q=[]
  heapq.heappush(q,(0,l))
  while len(q)>0:
    t = heapq.heappop(q)
    for x in v[t[0]]:
      # hit
      if cost[x[0]][t[1]] > cost[t[0]][t[1]]+x[2]:
        cost[x[0]][t[1]] = cost[t[0]][t[1]]+x[2]
        q.append((x[0], t[1]))
      # guard
      if t[1]-x[1]>=0 and cost[x[0]][t[1]-x[1]] > cost[t[0]][t[1]]:
        cost[x[0]][t[1]-x[1]] = cost[t[0]][t[1]]
        q.append((x[0], t[1]-x[1]))
  print min(cost[n-1])

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
N, M, L = inpl()

while N:
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, d, e = inpl()
        G[a].append([b, d, e])
        G[b].append([a, d, e])

    Q = [[0, 0, 1]] # bandits, distance, where
    cost = [[10**6]*(L+1) for _ in range(N+1)]
    cost[1][0] = 0
    while Q:
        e, d, p = heappop(Q)
        if cost[p][d] < e:
            continue
        if p == N:
            print(e)
            break
        for q, dd, de in G[p]:
            if d + dd <= L and e < cost[q][d+dd]:
                heappush(Q, (e, d+dd, q))
                cost[q][d+dd] = e
            if e + de < cost[q][d]:
                heappush(Q, (e+de, d, q))
                cost[q][d] = e+de
    N, M, L = inpl()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
import heapq
class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v, w in self.list[u]:
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

while True:
	n, m, l = map(int, input().split())
	if n == 0:
		break
	adj = [[] for _ in range(n*(l+1))]
	for _ in range(m):
		a, b, d, e = map(int, input().split())
		a, b = a-1, b-1
		for i in range(l+1):
			adj[i*n + a].append((i*n + b, e))
			adj[i*n + b].append((i*n + a, e))
			if i >= d:
				adj[i*n + a].append(((i-d)*n + b, 0))
				adj[i*n + b].append(((i-d)*n + a, 0))

	dijk = DijkstraList(adj, l*n)
	dijk.solve()
	ans = 10**7
	for i in range(l+1):
		ans = min(ans, dijk.dist[i*n + n-1])
	print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
def solve(readline=sys.stdin.readline, write=sys.stdout.write):
    N, M, L = map(int, readline().split())
    if N == 0:
        return 0
    G = [[] for i in range(N)]
    for i in range(M):
        a, b, d, e = map(int, readline().split())
        a -= 1; b -= 1
        G[a].append((b, d, e))
        G[b].append((a, d, e))

    INF = 10**9
    cost = [[INF]*(L+1) for i in range(N)]
    que = [(0, 0, 0)]
    cost[0][0] = 0
    while que:
        c, v, l = heappop(que)
        dv = cost[v][l]
        if c < dv:
            continue
        if v == N-1:
            break
        for w, d, e in G[v]:
            cw = cost[w]
            if l + d <= L and dv < cw[l + d]:
                cw[l + d] = dv
                heappush(que, (dv, w, l+d))
            if dv + e < cw[l]:
                cw[l] = dv + e
                heappush(que, (dv + e, w, l))
    write("%d\n" % min(cost[N-1]))
    return 1

while solve():
    ...

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from heapq import heappop, heappush
from collections import defaultdict

def inpl(): return list(map(int, input().split()))
N, M, L = inpl()

while N:
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, d, e = inpl()
        G[a].append([b, d, e])
        G[b].append([a, d, e])

    Q = [[0, 0, 1]] # bandits, distance, where
    visited = defaultdict(lambda : False)
    visited[(0, 0, 1)] = True
    
    while Q:
        e, d, p = heappop(Q)
        if p == N:
            print(e)
            break
        for q, dd, de in G[p]:
            if d + dd <= L and not visited[(e, d+dd, q)]:
                heappush(Q, (e, d+dd, q))
                visited[(e, d+dd, q)] = True
            if not visited[(e+de, d, q)]:
                heappush(Q, (e+de, d, q))
                visited[(e+de, d, q)] = True
    N, M, L = inpl()