fork download
copy 
  1. def solve() -> None:
  2.     n, m = invr()
  3.  
  4.     graph: list[list[tuple[int, int, int]]] = [[] for _ in range(n)]
  5.     goated_tunnels: set[tuple[int, int]] = set()
  6.     sum_c: int = 0
  7.     for i in range(m):
  8.         a, b, c, r = invr()
  9.         a -= 1
  10.         b -= 1
  11.         sum_c += c
  12.         graph[a].append((b, c, r))
  13.         graph[b].append((a, c, r))
  14.         if r > c:
  15.             goated_tunnels.add((a, b))
  16.             goated_tunnels.add((b, a))
  17.  
  18.     low: int = 0
  19.     high: int = sum_c
  20.  
  21.     def check(mid: int) -> bool:
  22.         stack: list[tuple[int, int]] = [(-mid, 0)]  # (-coins, node)
  23.         visited: set[int] = set()  # (node: coins)
  24.         while stack:
  25.             coins: int
  26.             node: int
  27.             coins, node = heapq.heappop(stack)
  28.             coins = -coins
  29.             if node in visited:
  30.                 continue
  31.             visited.add(node)
  32.             for neighbour, cost, reward in graph[node]:
  33.                 if coins >= cost:
  34.                     if (node, neighbour) in goated_tunnels:
  35.                         return True
  36.                     if neighbour == n - 1:
  37.                         return True
  38.                     if neighbour not in visited:
  39.                         heapq.heappush(stack, (-(coins - cost + reward), neighbour))
  40.         return False
  41.  
  42.     while low < high:
  43.         mid: int = (low + high) // 2
  44.         if check(mid):
  45.             high = mid
  46.         else:
  47.             low = mid + 1
  48.  
  49.     print(low)
  50.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class, interface, or enum expected
def solve() -> None:
^
Main.java:22: error: illegal character: '#'
        stack: list[tuple[int, int]] = [(-mid, 0)]  # (-coins, node)
                                                    ^
Main.java:23: error: illegal character: '#'
        visited: set[int] = set()  # (node: coins)
                                   ^
3 errors
stdout
copy 
Standard output is empty
https://ideone.com/bD1y6V
language:
Java (HotSpot 12)
created:
316 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!