結果

問題 No.3013 ハチマキ買い星人
ユーザー nasutarou1341
提出日時 2025-01-25 14:43:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,383 ms / 2,000 ms
コード長 2,758 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 184,436 KB
最終ジャッジ日時 2025-01-25 23:28:52
合計ジャッジ時間 29,599 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
pop = heapq.heappop
push = heapq.heappush

class GraphDataUndirected:
  def __init__(s, N):
    s.N = N
    s.AdjacencyList = [[] for _ in range(N + 1)]
    s.defind_egde = [0] * (s.N + 1)
  def add_edge(s, a, b, x):
    s.AdjacencyList[a].append([x, b])
    s.AdjacencyList[b].append([x, a])
    s.defind_egde[a] = 1
    s.defind_egde[b] = 1
  def add_edges(s, list):
    for a, b, x in list:
      s.add_edge(a, b, x)
  def get_edges(s):
    ans = []
    for frm in range(len(s.AdjacencyList)):
      for value, to in s.AdjacencyList[frm]:
        ans.append([frm, to, value])
    return ans
  def getDijkstra(s):
    return DijkstraUndirected(s.N, s.AdjacencyList)

class DijkstraUndirected:
  def __init__(s, N, AdjacencyList):
    s.N = N
    s.AdjacencyList = AdjacencyList

  def dist(s, start):
    list = s.AdjacencyList
    D = [-1] * (s.N + 1) # その頂点までの距離
    path_count_data = [0] * (s.N + 1) # その頂点までの経路数
    path_count_data[start] = 1
    q  = []
    push(q, (0, start, -1))
    while q:
      d, x, t = pop(q)
      if D[x] != -1:
        if D[x] == d : path_count_data[x] += path_count_data[t]
        continue
      if t != -1: path_count_data[x] += path_count_data[t]
      D[x] = d
      for j, i in list[x]:
        if D[i] != -1:
          if D[i] == d + j: path_count_data[i] += path_count_data[x]
          continue
        push(q, (d + j, i, x))
    return D, path_count_data
  
  def get_bridge(s, start, goal, nodes):
    way_there, path_count_there = s.dist(start)
    way_back, path_count_back = s.dist(goal)
    way_length = way_there[goal]
    path_count = path_count_there[goal]
    N = len(nodes)
    ans = [0] * N
    for i, (x, y, value) in enumerate(nodes):
      for frm, to in [[x, y], [y, x]]:
        a = way_there[frm]
        n = path_count_there[frm]
        b = way_back[to]
        m = path_count_back[to]
        if a + b + value == way_length and n * m == path_count: ans[i] = 1
    return ans
  
  def get_shortest_path_graph(s, start, goal):
    way_there, _ = s.dist(start)
    way_back, _ = s.dist(goal)
    way_length = way_there[goal]
    Graph = GraphDataUndirected(s.N)
    for frm in range(len(s.AdjacencyList)):
      a = way_there[frm]
      for value, to in s.AdjacencyList[frm]:
        b = way_back[to]
        if a + b + value == way_length: Graph.add_edge(frm, to, value)
    return Graph

N, M, P, Y = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]
DE = [list(map(int, input().split())) for _ in range(P)]

gf = GraphDataUndirected(N)
gf.add_edges(ABC)
D = gf.getDijkstra()

L = D.dist(1)[0]
ans = 0
for d, e in DE:
  if L[d] == -1: continue
  y = Y - L[d]
  a = y // e
  ans = max(ans, a)

print(ans)
0