結果

問題 No.3013 ハチマキ買い星人
ユーザー nasutarou1341
提出日時 2025-01-25 13:47:35
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,694 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 185,184 KB
最終ジャッジ日時 2025-01-25 22:59:26
合計ジャッジ時間 29,705 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 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


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

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

  @staticmethod
  def makeDijkstra(gf : GraphDataUndirected):
    return DijkstraUndirected(gf.N, gf.AdjacencyList)

  def dist(self, start):
    list = self.AdjacencyList
    D = [-1] * (self.N + 1) # その頂点までの距離
    path_count_data = [0] * (self.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(self, start, goal, nodes):
    way_there, path_count_there = self.dist(start)
    way_back, path_count_back = self.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(self, start, goal):
    way_there, _ = self.dist(start)
    way_back, _ = self.dist(goal)
    way_length = way_there[goal]
    Graph = GraphDataUndirected(self.N)
    for frm in range(len(self.AdjacencyList)):
      a = way_there[frm]
      for value, to in self.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 = DijkstraUndirected.makeDijkstra(gf)

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

print(ans)
0