bitwick

The dragons are just indices.

‹ back to the board

Wednesday, September 30

Adeptalgorithms & data structures

The Writs of Free Passage

The toll-roads out of bitwick are held by waystation keepers, and the courier's guild issues writs of free passage: one writ buys one crossing with no toll paid. A courier is leaving the town gate with a satchel of writs and needs the cheapest way out to the far waystation.

Write minToll(n, roads, passes).

  • n is an integer, the number of waystations, numbered 0 to n - 1 (n >= 1). The courier starts at 0 and must reach n - 1.
  • roads is a list of triples [a, b, toll]. Each triple is one two-way road between the distinct waystations a and b, costing toll coins to cross in either direction. toll is an integer >= 0. There may be more than one road between the same pair of waystations.
  • passes is an integer >= 0, the number of writs carried. Each writ may be spent on a single crossing of a single road, making that crossing cost 0 coins. A writ is used up when spent, and writs need not all be spent.

Waystations and roads may be visited and crossed any number of times.

Return the smallest total number of coins paid on a journey from waystation 0 to waystation n - 1, as an integer, or -1 if no such journey exists.

  • graph traversal
  • Adept

examples

  1. case 1n of 3, roads of [[0, 2, 100], [0, 1, 7], [1, 2, 7]], passes of 10 — the single road 0-2 costs 100 coins, but one writ waives that crossing entirely; the two-road route would still cost 7 coins after a writ
  2. case 2n of 4, roads of [[0, 1, 10], [1, 2, 10], [2, 3, 10]], passes of 120 — three crossings are unavoidable and one of them is free
  3. case 3n of 4, roads of [[0, 1, 5], [2, 3, 4]], passes of 2-1 — no journey reaches waystation 3
  4. case 4n of 1, roads of [], passes of 00 — the courier is already at the destination
reward
310 XP
signature
minToll
not yet run

TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.

loading the editor…
  • already at the destination
  • no route exists
  • a writ on the costliest road
  • no writs at all
  • two writs change the route
  • more writs than crossings
  • a free road on the way
  • the long ladder of paired roads
The Writs of Free Passage · bitwick