shortest-paths

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.8 Finding Shortest Paths in Directed Acyclic Graphs

10.8 Finding Shortest Paths in Directed Acyclic Graphs Many shortest-path algorithms are designed to handle arbitrary graphs. They must deal with cycles, repeated visits, and complex path structures. Directed acyclic graphs (DAGs) are different. Since DAGs contain no cycles, shortest paths become significantly easier to compute. In fact, shortest paths in a DAG can be found in linear time. This is faster than Dijkstra, faster than Bellman-Ford, and often simpler...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall The algorithms covered so far solve the single-source shortest path problem. Given a source vertex, they compute the shortest distance to every other vertex. Sometimes that is not enough. A routing system may need distances between every pair of cities. A graph analytics engine may need the shortest distance between every pair of users. A database optimizer may repeatedly ask shortest-path questions between...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.2 Finding Shortest Paths with BFS

10.2 Finding Shortest Paths with BFS Use BFS when every edge has the same cost. In that setting, the shortest path is the path with the fewest edges, and BFS finds it by exploring the graph one distance layer at a time. This recipe focuses on the standard single-source BFS form: given a source vertex, compute the shortest distance to every reachable vertex. Problem Given an unweighted graph and a...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.20 Choosing the Right Shortest-Path Algorithm

10.20 Choosing the Right Shortest-Path Algorithm This chapter introduced a substantial collection of shortest-path algorithms. At first glance, the algorithms may appear unrelated. Some use queues. Some use priority queues. Some use dynamic programming. Some rely on graph transformations. Some use heuristics. In practice, the most important skill is not memorizing every algorithm. It is recognizing which algorithm fits a particular problem. This recipe summarizes the major shortest-path techniques and...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.25 Debugging and Optimizing Shortest-Path Code

10.25 Debugging and Optimizing Shortest-Path Code Shortest-path code usually fails in predictable ways. The algorithm may be conceptually correct, but the implementation mishandles the queue, marks vertices at the wrong time, overflows an integer, reconstructs paths incorrectly, or applies the algorithm outside its assumptions. This final recipe provides a practical checklist for debugging and optimizing shortest-path implementations. Problem Given a shortest-path implementation that is wrong, slow, or memory-heavy, identify the...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS Between ordinary BFS and Dijkstra lies an interesting class of shortest-path problems. Suppose edge weights are restricted to only two values: 0 1 Many practical problems naturally have this structure. A routing system may assign cost 0 to preferred roads and cost 1 to secondary roads. A state-space search may assign cost 0 to free transitions and cost 1 to costly...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.23 Common Shortest-Path Patterns and Interview Problems

10.23 Common Shortest-Path Patterns and Interview Problems Learning shortest-path algorithms is only the first step. The next challenge is recognizing when a problem can be solved using them. Many interview questions, programming contests, and production systems disguise shortest-path problems behind different stories: Mazes Transformations Scheduling Navigation Resource optimization State exploration The underlying graph is often hidden. This recipe presents the most common shortest-path patterns and shows how to identify them...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.17 Finding K Shortest Paths

10.17 Finding K Shortest Paths Most shortest-path algorithms answer a single question: What is the shortest path from the source to the destination? In many practical systems, one path is not enough. A navigation application may want alternative routes. A logistics system may need backup delivery plans. A network router may require secondary paths in case of failures. A recommendation engine may want multiple high-quality options rather than a single...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm Breadth-first search works because every edge contributes the same cost. Once edge weights become arbitrary positive values, distance layers disappear. A path containing fewer edges may be more expensive than a path containing many edges. Consider the following graph: A --1-- B --1-- D \ ^ \ / 5 1 \ / C ----- The path: A -> C -> D...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.24 Testing Shortest-Path Implementations

10.24 Testing Shortest-Path Implementations Shortest-path implementations are prone to subtle errors. A small example may pass even when the algorithm mishandles unreachable vertices, duplicate edges, zero-weight edges, negative edges, or path reconstruction. Testing shortest-path code requires more than checking one happy path. Good tests should exercise the assumptions of the algorithm and the invariants used in its correctness proof. This recipe presents a practical testing strategy for BFS, Dijkstra, Bellman-Ford,...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.5 Detecting Negative Edges with Bellman-Ford

10.5 Detecting Negative Edges with Bellman-Ford Dijkstra's algorithm depends on a crucial assumption: edge weights must be nonnegative. Once negative edges enter the graph, the greedy strategy that makes Dijkstra efficient no longer works. A path that appears optimal today may become cheaper tomorrow through a negative-weight edge discovered later. Bellman-Ford takes a different approach. Instead of greedily finalizing distances, it repeatedly relaxes every edge in the graph until no...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.6 Detecting Negative Cycles with Bellman-Ford

10.6 Detecting Negative Cycles with Bellman-Ford In the previous recipe, Bellman-Ford was used to compute shortest paths in graphs that contain negative edge weights. The algorithm included an additional pass that detected negative cycles, but the detection itself deserves a closer look. Negative cycles are fundamentally different from ordinary graph structures. A shortest path normally represents a minimum cost route between two vertices. A negative cycle destroys that concept. If...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.12 Accelerating Searches with Bidirectional Search

10.12 Accelerating Searches with Bidirectional Search Many shortest-path algorithms begin at the source and gradually expand outward until the target is reached. This works well, but it often explores far more of the graph than necessary. Consider finding a route between two cities on opposite sides of a large road network. A traditional search expands a growing region from the source. Much of that exploration occurs far from the destination....

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.14 Using Distance Labels and Relaxation Correctly

10.14 Using Distance Labels and Relaxation Correctly Every shortest-path algorithm in this chapter appears different on the surface. BFS uses a queue. Dijkstra uses a priority queue. Bellman-Ford repeatedly scans edges. Floyd-Warshall uses dynamic programming. A* uses heuristics. Despite these differences, they all rely on the same fundamental idea: Distance labels are gradually improved through relaxation. Understanding this idea provides a unified framework for reasoning about shortest-path algorithms. Instead of...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.21 Proving Correctness of Shortest-Path Algorithms

10.21 Proving Correctness of Shortest-Path Algorithms Shortest-path algorithms are easy to implement incorrectly. A program may pass small examples while failing on edge cases involving cycles, unreachable vertices, zero-weight edges, or negative weights. Correctness proofs prevent this kind of accidental confidence. This recipe develops the proof patterns used for shortest-path algorithms. The goal is not formal theorem proving. The goal is to learn the invariants that explain why an algorithm...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.22 Analyzing Complexity of Shortest-Path Algorithms

10.22 Analyzing Complexity of Shortest-Path Algorithms Shortest-path algorithms are often chosen by correctness first, then by complexity. Once the graph model and edge weights determine which algorithms are valid, the next question is performance. This recipe explains how to analyze shortest-path algorithms using the two standard graph parameters: V = number of vertices E = number of edges The goal is to understand where the running time comes from, not...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.13 Reconstructing Shortest Paths

10.13 Reconstructing Shortest Paths Most shortest-path algorithms compute distances. They tell us that the minimum cost from a source to a destination is: 17 or: 42 In practice, this information is often insufficient. A navigation system must display the route. A network router must know which links to traverse. A workflow engine must know which sequence of tasks leads to the optimal outcome. The actual path is frequently more important...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.18 Solving Shortest Paths on Grids

10.18 Solving Shortest Paths on Grids Many shortest-path problems are not given as explicit graph structures. Instead, they appear as grids. A grid may represent a maze, a game map, a warehouse floor, a robot workspace, an image, or a terrain model. Cells are vertices. Valid moves between neighboring cells are edges. Once you make that translation, ordinary graph algorithms apply directly. This recipe shows how to model grid shortest-path...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.9 Computing Multi-Source Shortest Paths

10.9 Computing Multi-Source Shortest Paths Most shortest-path problems begin with a single source vertex. We start at one location and ask for the shortest distance to every other location. Some problems are naturally different. A city may contain multiple hospitals, and we want the nearest hospital for every neighborhood. A game map may contain multiple spawn points, and we want the closest one for each position. A logistics network may...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.15 Using Potentials to Reweight Graphs

10.15 Using Potentials to Reweight Graphs Negative edge weights complicate shortest-path algorithms. Dijkstra's algorithm is efficient because it assumes that once a vertex receives the smallest tentative distance, that distance can never improve. Negative edges break this assumption. A path that appears expensive today may become cheaper tomorrow after traversing a negative edge. Bellman-Ford handles negative edges correctly, but its running time is significantly higher than Dijkstra's. This raises an...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.19 Modeling State-Space Problems as Shortest Paths

10.19 Modeling State-Space Problems as Shortest Paths One of the most powerful ideas in algorithm design is that many problems that do not look like graph problems can be transformed into shortest-path problems. A maze is obviously a graph. A puzzle is less obvious. A scheduling problem is even less obvious. A string transformation problem may not appear graph-related at all. Yet many of these problems become straightforward once we...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm The shortest-path algorithms studied so far naturally divide into two groups. Single-source algorithms: BFS Dijkstra Bellman-Ford DAG shortest paths A* All-pairs algorithms: Floyd-Warshall When a graph contains thousands or millions of vertices, Floyd-Warshall's cubic running time often becomes impractical. Running Dijkstra from every vertex can be much faster for sparse graphs, but negative edge weights create complications. Johnson's algorithm combines several...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.4 Implementing Dijkstra with Priority Queue Variants

10.4 Implementing Dijkstra with Priority Queue Variants The previous recipe used Dijkstra’s algorithm with a binary heap and lazy deletion. That version is the usual choice in production code because it is simple, fast enough for most sparse graphs, and available in standard libraries. This recipe compares three implementation variants: Linear scan Binary heap with lazy deletion Indexed priority queue with decrease-key The algorithmic idea remains the same. The difference...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.11 Accelerating Search with A

10.11 Accelerating Search with A Dijkstra's algorithm finds shortest paths by expanding vertices in order of increasing distance from the source. This guarantees correctness, but it often explores large portions of the graph that are irrelevant to the final answer. Suppose you want driving directions from one city to another. Dijkstra expands outward in every direction, including areas that move away from the destination. Many of those vertices will never...

Programming › Algorithm Cookbook › Chapter 10. Shortest Paths ›

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search Breadth-first search (BFS) is the simplest shortest path algorithm. When every edge in a graph has the same cost, BFS discovers vertices in increasing order of distance from the starting vertex. The first time a vertex is reached, the algorithm has already found the shortest possible path to it. This property makes BFS one of the most important graph algorithms....

Programming › Algorithm Cookbook ›

Chapter 10. Shortest Paths

Practice › Codeforces Solutions › Codeforces Round 942 (Div. 1) ›

CF 1967D - Long Way to be Non-decreasing

CF 1967D - Long Way to be Non-decreasing Rating: 2800 Tags: binary search, dfs and similar, graphs, implementation, shortest paths, two pointers Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given an array where each position contains a value in the range $1$ to $m$, and a second array that defines a deterministic transformation on values: every value $x$ has a fixed replacement $b_x$. One operation, called...

Practice › Codeforces Solutions › Educational Codeforces Round 163 (Rated for Div. 2) ›

CF 1948C - Arrow Path

CF 1948C - Arrow Path Rating: 1300 Tags: brute force, constructive algorithms, dfs and similar, dp, graphs, shortest paths Solve time: 56s Verified: yes Solution Problem Understanding We have a 2-row grid with $n$ columns, and each cell contains an arrow pointing either left or right. The robot starts at the top-left corner, and each second it first moves to an adjacent cell (up, down, left, right) and then follows...

Practice › Codeforces Solutions › Codeforces Round 938 (Div. 3) ›

CF 1955H - The Most Reckless Defense

CF 1955H - The Most Reckless Defense Rating: 2300 Tags: bitmasks, brute force, constructive algorithms, dp, flows, graph matchings, shortest paths Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a grid where some cells form a fixed path from the top-left corner to the bottom-right corner. An enemy walks along this path one cell per second. At each cell, it spends a full second there, and...

Practice › Codeforces Solutions ›

Educational Codeforces Round 163 (Rated for Div. 2)

Educational Codeforces Round 163 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-3100 | Time: 11m 57s Problem Name Rating Tags Solve Time Verified A Special Characters 800 brute-force, constructive-algorithms 1m 17s ✗ C Arrow Path 1300 brute-force, constructive-algorithms, dfs-and-similar 56s ✓ D Tandem Repeats? 1700 brute-force, strings, two-pointers 2m 48s ✗ E Clique Partition 2100 brute-force, constructive-algorithms, graphs 2m 41s ✗...

Practice › Codeforces Solutions › Codeforces Round 947 (Div. 1 + Div. 2) ›

CF 1975D - Paint the Tree

CF 1975D - Paint the Tree Rating: 1700 Tags: brute force, dfs and similar, dp, greedy, shortest paths, trees Solve time: 5m 19s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 257 (Div. 1)

Codeforces Round 257 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1700-2900 | Time: 9m 38s Problem Name Rating Tags Solve Time Verified A Jzzhu and Chocolate 1700 greedy, math 2m 1s ✓ B Jzzhu and Cities 2000 graphs, greedy, shortest-paths 1m 26s ✓ C Jzzhu and Apples 2500 constructive-algorithms, number-theory 1m 44s ✗ D Jzzhu and Numbers 2400 bitmasks, combinatorics, dp 1m 54s...

Practice › Codeforces Solutions › Codeforces Round 270 ›

CF 472D - Design Tutorial: Inverse the Problem

CF 472D - Design Tutorial: Inverse the Problem Rating: 1900 Tags: dfs and similar, dsu, shortest paths, trees Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given an $n \times n$ matrix where each entry $d[i][j]$ represents the distance between nodes $i$ and $j$. The question asks whether there exists a weighted tree with $n$ nodes such that the distance along the tree between any two nodes...

Practice › Codeforces Solutions ›

Codeforces Round 270

Codeforces Round 270 Type: Special | Problems: 7 | Verified: 5/7 | Rating range: 800-2800 | Time: 12m 18s Problem Name Rating Tags Solve Time Verified A Design Tutorial: Learn from Math 800 math, number-theory 1m 22s ✓ B Design Tutorial: Learn from Life 1300 - 1m 44s ✓ C Design Tutorial: Make It Nondeterministic 1400 greedy 1m 16s ✓ D Design Tutorial: Inverse the Problem 1900 dfs-and-similar, dsu, shortest-paths...

Practice › Codeforces Solutions › Codeforces Round 265 (Div. 1) ›

CF 464E - The Classic Problem

CF 464E - The Classic Problem Rating: 3000 Tags: data structures, graphs, shortest paths Solve time: 5m 14s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 263 (Div. 1) ›

CF 461E - Appleman and a Game

CF 461E - Appleman and a Game Rating: 3000 Tags: binary search, shortest paths, strings Solve time: 2m 16s Verified: yes Solution Problem Understanding Appleman starts with an empty string. In one second he may append any substring of t to the end of the string he is building. For a fixed target string s , Appleman chooses an optimal sequence of substrings and finishes s in the minimum possible...

Practice › Codeforces Solutions › Codeforces Round 257 (Div. 1) ›

CF 449B - Jzzhu and Cities

CF 449B - Jzzhu and Cities Rating: 2000 Tags: graphs, greedy, shortest paths Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given an undirected weighted graph representing cities and roads. City 1 is the capital. In addition to normal roads, there are special train routes that connect the capital directly to some city. The government wants to close as many train routes as possible. The restriction is...

Practice › Codeforces Solutions › Codeforces Round 148 (Div. 1) ›

CF 238E - Meeting Her

CF 238E - Meeting Her Rating: 2600 Tags: dp, graphs, shortest paths Solve time: 3m 19s Verified: no Solution Problem Understanding We are given a directed graph representing a city with junctions and streets. Urpal starts at junction a and wants to reach junction b using buses. Each bus is controlled by a company and at every second, it randomly chooses a shortest path from its start junction s_i to...

Practice › Codeforces Solutions › Codeforces Round 142 (Div. 1) ›

CF 229B - Planets

CF 229B - Planets Rating: 1700 Tags: binary search, data structures, graphs, shortest paths Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given an undirected weighted graph of planets connected by stargates. Jack starts on planet 1 at time 0 and wants to reach planet n as early as possible. Moving through a stargate takes a fixed positive amount of time. The unusual part is the waiting...

Practice › Codeforces Solutions › Croc Champ 2012 - Round 1 ›

CF 173B - Chamber of Secrets

CF 173B - Chamber of Secrets Rating: 1800 Tags: dfs and similar, shortest paths Solve time: 1m 49s Verified: yes Solution Problem Understanding The Chamber of Secrets is represented as a grid of size n by m , where each cell is either empty or contains a column. A basilisk is stationed in the bottom-right corner and looks left, while a person trying to enter starts at the top-left corner...

Practice › Codeforces Solutions ›

Croc Champ 2012 - Round 1

Croc Champ 2012 - Round 1 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1300-2600 | Time: 10m 55s Problem Name Rating Tags Solve Time Verified A Rock-Paper-Scissors 1300 implementation, math 1m 40s ✓ B Chamber of Secrets 1800 dfs-and-similar, shortest-paths 1m 49s ✓ C Spiral Maximum 1900 brute-force, dp 2m 41s ✗ D Deputies 2500 constructive-algorithms, graphs, greedy 3m 4s ✓ E Camping Groups 2600 data-structures,...

Practice › Codeforces Solutions › Codeforces Round 124 (Div. 1) ›

CF 196E - Opening Portals

CF 196E - Opening Portals Rating: 2600 Tags: dsu, graphs, shortest paths Solve time: 2m 19s Verified: yes Solution Problem Understanding We are asked to compute the minimum time needed for a player to open all portals in a country modeled as a graph. The country consists of n cities connected by m bidirectional roads with positive travel times. Some subset of cities, k of them, have portals. Initially, all...

Practice › Codeforces Solutions ›

Codeforces Round 179 (Div. 1)

Codeforces Round 179 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1700-2500 | Time: 11m 55s Problem Name Rating Tags Solve Time Verified B Greg and Graph 1700 dp, graphs, shortest-paths 6m 5s ✓ C Greg and Friends 2100 combinatorics, dp, graphs 2m 44s ✓ D Greg and Caves 2400 combinatorics, dp 1m 37s ✓ E Yaroslav and Points 2500 data-structures 1m 29s ✓

Practice › Codeforces Solutions › Codeforces Round 119 (Div. 1) ›

CF 187B - AlgoRace

CF 187B - AlgoRace Rating: 1800 Tags: dp, shortest paths Solve time: 2m 5s Verified: yes Solution Problem Understanding We have a complete directed graph on n cities. For every car type, we know the travel time between every ordered pair of cities. These travel times are not guaranteed to be symmetric, so going from u to v may cost something different than going from v to u . A...

Practice › Codeforces Solutions › Codeforces Round 115 ›

CF 175F - Gnomes of Might and Magic

CF 175F - Gnomes of Might and Magic Rating: 3000 Tags: data structures, graphs, implementation, shortest paths Solve time: 1m 50s Verified: yes Solution Problem Understanding The kingdom of gnomes consists of castles connected by a very specific graph structure. There is a cycle of m castles called the Good Path, connected sequentially with roads and forming a closed loop. Between every pair of consecutive castles on this cycle, there...

Practice › Codeforces Solutions ›

Codeforces Round 182 (Div. 1)

Codeforces Round 182 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1800-2800 | Time: 17m 11s Problem Name Rating Tags Solve Time Verified A Yaroslav and Sequence 1800 constructive-algorithms 1m 30s ✓ B Yaroslav and Time 2100 binary-search, graphs, shortest-paths 2m 10s ✓ C Yaroslav and Algorithm 2500 constructive-algorithms 6m 58s ✓ D Yaroslav and Divisors 2200 data-structures 2m 55s ✓ E Yaroslav and...

Practice › Codeforces Solutions › Codeforces Round 154 (Div. 2) ›

CF 253C - Text Editor

CF 253C - Text Editor Rating: 1600 Tags: data structures, dfs and similar, graphs, greedy, shortest paths Solve time: 53s Verified: yes Solution Problem Understanding We are given a text editor that stores several lines of text. Each line has a known length, and the cursor is allowed to sit not only on characters but also in the gap positions before the first character and after the last character. So...

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295B - Greg and Graph

CF 295B - Greg and Graph Rating: 1700 Tags: dp, graphs, shortest paths Solve time: 6m 5s Verified: yes Solution Problem Understanding We are given a fully connected directed graph with weighted edges, represented as an adjacency matrix. Each vertex has an edge to every other vertex, including a zero-weight self-loop. Greg wants to play a game where he removes vertices one by one according to a given sequence. Before...

Practice › Codeforces Solutions › Codeforces Round 103 (Div. 2) ›

CF 144D - Missile Silos

CF 144D - Missile Silos Rating: 1900 Tags: data structures, dfs and similar, graphs, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a connected weighted undirected graph representing cities and roads. City s is the capital. A missile silo may be located either exactly on a city or at some interior point of a road. A position is valid if its shortest-path distance to...

Practice › Codeforces Solutions › Codeforces Round 185 (Div. 1) ›

CF 311C - Fetch the Treasure

CF 311C - Fetch the Treasure Rating: 2500 Tags: brute force, data structures, graphs, shortest paths Solve time: 1m 7s Verified: yes Solution Problem Understanding We have a linear arrangement of h cells, numbered from 1 to h . Some of these cells contain treasures, each with a positive dollar value. Freda starts at the first cell and initially has only one step size, k , allowing her to move...

Practice › Codeforces Solutions ›

Codeforces Round 119 (Div. 1)

Codeforces Round 119 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 4/5 | Rating range: 1500-2900 | Time: 10m 3s Problem Name Rating Tags Solve Time Verified A Permutations 1500 greedy 1m 30s ✓ B AlgoRace 1800 dp, shortest-paths 2m 5s ✓ C Weak Memory 2000 dfs-and-similar, dsu 2m 12s ✓ D BRT Contract 2800 data-structures 1m 54s ✓ E Heaven Tour 2900 data-structures, greedy 2m 22s ✗

Practice › Codeforces Solutions ›

Codeforces Round 117 (Div. 2)

Codeforces Round 117 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2200 | Time: 11m 48s Problem Name Rating Tags Solve Time Verified A Battlefield 2200 geometry, graphs, implementation 3m 47s ✓ B Vasya's Calendar 1000 implementation 3m 18s ✗ C Optimal Sum 2000 data-structures, greedy 1m 50s ✓ D Common Divisors 1400 brute-force, hashing, implementation 1m 36s ✓ E Wooden Fence 1800 dp...

Practice › Codeforces Solutions › Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) ›

CF 241E - Flights

CF 241E - Flights Rating: 2600 Tags: graphs, shortest paths Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given a directed acyclic graph of cities and one-way flights. Every flight initially takes 1 hour. We may independently change any flight duration to either 1 or 2 hours. The goal is to assign durations so that every possible path from city 1 to city n has exactly the...

Practice › Codeforces Solutions › Codeforces Round 149 (Div. 2) ›

CF 242C - King's Path

CF 242C - King's Path Rating: 1800 Tags: dfs and similar, graphs, hashing, shortest paths Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a huge implicit grid, up to $10^9 \times 10^9$, but only a small subset of cells are usable. Each usable region is given as a horizontal segment: a row number and a contiguous interval of columns. Taken together, these segments define a sparse...

Practice › Codeforces Solutions › Codeforces Round 163 (Div. 2) ›

CF 266B - Queue at the School

CF 266B - Queue at the School Rating: 800 Tags: constructive algorithms, graph matchings, implementation, shortest paths Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a queue made of boys and girls, represented as a string containing only B and G . Every second, each adjacent pair "BG" swaps positions and becomes "GB" . The swaps happen simultaneously. That detail matters a lot. If a boy...

Practice › Codeforces Solutions › Codeforces Round 155 (Div. 2) ›

CF 254D - Rats

CF 254D - Rats Rating: 2300 Tags: brute force, dfs and similar, graphs, implementation, shortest paths Solve time: 3m 1s Verified: no Solution Problem Understanding The problem presents a rectangular basement of a store as an n × m grid, where some cells are walls, some are empty, and some contain sleeping rats. Vasily has two grenades, and when a grenade explodes in a cell, its blast propagates outward to...

Practice › Codeforces Solutions › Codeforces Round 117 (Div. 2) ›

CF 182A - Battlefield

CF 182A - Battlefield Rating: 2200 Tags: geometry, graphs, implementation, shortest paths Solve time: 3m 47s Verified: yes Solution Problem Understanding We are asked to simulate movement across a 2D plane from a starting point $A$ to a destination $B$ while avoiding a periodic laser. The laser alternates between charging and firing, with durations $a$ and $b$ seconds, respectively. During the firing phase, Vasya must be inside a trench to...

Practice › Codeforces Solutions ›

Codeforces Round 130 (Div. 2)

Codeforces Round 130 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 900-2100 | Time: 4m 49s Problem Name Rating Tags Solve Time Verified A Dubstep 900 strings 59s ✓ C Police Station 1900 dp, graphs, shortest-paths 1m 18s ✓ D Prizes, Prizes, more Prizes 1200 implementation 1m 26s ✓ E Blood Cousins 2100 binary-search, data-structures, dfs-and-similar 1m 6s ✓

Practice › Codeforces Solutions ›

Codeforces Round 163 (Div. 2)

Codeforces Round 163 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 2/4 | Rating range: 800-2500 | Time: 8m 10s Problem Name Rating Tags Solve Time Verified B Queue at the School 800 constructive-algorithms, graph-matchings, implementation 1m 21s ✓ C Below the Diagonal 2100 constructive-algorithms, greedy, math 2m 17s ✗ D BerDonalds 2400 graphs, math, shortest-paths 2m 9s ✗ E More Queries to Array... 2500 data-structures, math 2m...

Practice › Codeforces Solutions ›

Codeforces Round 103 (Div. 2)

Codeforces Round 103 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 8m 5s Problem Name Rating Tags Solve Time Verified A Arrival of the General 800 implementation 1m 52s ✓ B Meeting 1300 implementation 1m 15s ✓ C Anagram Search 1500 implementation, strings 1m 23s ✓ D Missile Silos 1900 data-structures, dfs-and-similar, graphs 2m 10s ✓ E Competition 2200 data-structures, greedy...

Practice › Codeforces Solutions › Codeforces Round 182 (Div. 1) ›

CF 301B - Yaroslav and Time

CF 301B - Yaroslav and Time Rating: 2100 Tags: binary search, graphs, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given a set of stations placed on a 2D grid. Moving between any two stations takes time proportional to their Manhattan distance multiplied by a constant factor $d$. Each station $i$ (except the first and last) provides a one-time bonus that increases our available time...

Practice › Codeforces Solutions › Codeforces Round 101 (Div. 2) ›

CF 141D - Take-off Ramps

CF 141D - Take-off Ramps Rating: 2300 Tags: graphs, shortest paths Solve time: 2m 15s Verified: yes Solution Problem Understanding We are moving on a one-dimensional track from position 0 to position L . Walking is simple, one meter costs exactly one second, and we may move in either direction as long as we never go below 0 . A ramp gives a shortcut, but using it has a strict...

Practice › Codeforces Solutions ›

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements) Type: ICPC/IOI | Problems: 4 | Verified: 3/4 | Rating range: 1900-2900 | Time: 7m 47s Problem Name Rating Tags Solve Time Verified D Numbers 2900 - 2m 21s ✗ E Flights 2600 graphs, shortest-paths 1m 54s ✓ F Race 2300 brute-force, implementation 2m 26s ✓ G Challenging Balloons 1900 constructive-algorithms 1m 6s ✓

Practice › Codeforces Solutions › Codeforces Round 241 (Div. 2) ›

CF 416E - President's Path

CF 416E - President's Path Rating: 2500 Tags: dp, graphs, shortest paths Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a graph with n cities connected by m bidirectional roads, each with a positive length. The goal is to determine, for every pair of cities (s, t) with s < t , how many roads can appear on at least one shortest path from s to...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232C - Doe Graphs

CF 232C - Doe Graphs Rating: 2600 Tags: constructive algorithms, divide and conquer, dp, graphs, shortest paths Solve time: 2m 23s Verified: yes Solution Problem Understanding The graph family is built recursively. D(0) is a single vertex. D(1) is a single edge. For every larger order, D(n) is formed by taking a copy of D(n-1) and a shifted copy of D(n-2) , then connecting them with two extra edges. The...

Practice › Codeforces Solutions › Codeforces Round 179 (Div. 1) ›

CF 295C - Greg and Friends

CF 295C - Greg and Friends Rating: 2100 Tags: combinatorics, dp, graphs, shortest paths Solve time: 2m 44s Verified: yes Solution Problem Understanding We are given a group of $n$ people standing on one river bank. Each person has a weight of either 50 or 100, and a boat that can carry a limited total weight $k$. Every time the boat crosses the river, it must carry at least one...

Practice › Codeforces Solutions › Codeforces Round 163 (Div. 2) ›

CF 266D - BerDonalds

CF 266D - BerDonalds Rating: 2400 Tags: graphs, math, shortest paths Solve time: 2m 9s Verified: no Solution Problem Understanding We are given a connected weighted undirected graph representing a road network. Junctions are graph vertices, roads are weighted edges, and the restaurant may be placed anywhere, not only at vertices but also at any point along an edge. For a chosen location, its quality is determined by the distance...

Practice › Codeforces Solutions › Codeforces Round 192 (Div. 1) ›

CF 329B - Biridian Forest

CF 329B - Biridian Forest Rating: 1500 Tags: dfs and similar, shortest paths Solve time: 2m 48s Verified: yes Solution Problem Understanding We are asked to navigate a forest represented as a grid. Each cell can be empty, contain a tree, or contain one or more mikemon breeders. Our goal is to move from our starting position to a designated exit while minimizing the number of battles we are forced...

Practice › Codeforces Solutions › Codeforces Round 188 (Div. 1) ›

CF 317E - Princess and Her Shadow

CF 317E - Princess and Her Shadow Rating: 3100 Tags: constructive algorithms, shortest paths Solve time: 1m 46s Verified: yes Solution Problem Understanding We are asked to simulate a chase on a two-dimensional grid between Princess Vlada and her playful Shadow. The grid is infinite but sparse trees are present, which act as obstacles. Both the Princess and Shadow start at distinct integer coordinates. Each turn, the Princess can move...

Practice › Codeforces Solutions ›

Codeforces Round 192 (Div. 1)

Codeforces Round 192 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 1500-3100 | Time: 7m 40s Problem Name Rating Tags Solve Time Verified A Purification 1500 constructive-algorithms, greedy 3m 58s ✗ B Biridian Forest 1500 dfs-and-similar, shortest-paths 2m 48s ✓ E Evil 3100 math 54s ✗

Practice › Codeforces Solutions ›

Codeforces Round 142 (Div. 1)

Codeforces Round 142 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 10m 59s Problem Name Rating Tags Solve Time Verified A Shifts 1500 brute-force, two-pointers 1m 34s ✓ B Planets 1700 binary-search, data-structures, graphs 1m 37s ✓ C Triangles 1900 combinatorics, graphs, math 2m 5s ✓ D Towers 2100 dp, greedy, two-pointers 2m 55s ✓ E Gifts 2600 combinatorics, dp, math...

Practice › Codeforces Solutions › Codeforces Round 130 (Div. 2) ›

CF 208C - Police Station

CF 208C - Police Station Rating: 1900 Tags: dp, graphs, shortest paths Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given an undirected, connected graph representing cities and roads. Every pair of cities is reachable, and each road has equal travel time. Among all pairs of cities, we are especially interested in shortest routes between city 1 and city n. Every shortest route is treated as equally...

Practice › Codeforces Solutions › Codeforces Beta Round 77 (Div. 1 Only) ›

CF 95C - Volleyball

CF 95C - Volleyball Rating: 1900 Tags: shortest paths Solve time: 1m 21s Verified: yes Solution Problem Understanding The problem presents a weighted undirected graph where nodes represent junctions and edges represent roads with a given length. At each junction, there is a taxi that can carry a passenger up to a maximum distance and charges a fixed cost. Petya wants to travel from a starting junction to a stadium...

Practice › Codeforces Solutions › Codeforces Beta Round 14 (Div. 2) ›

CF 14D - Two Paths

CF 14D - Two Paths Rating: 1900 Tags: dfs and similar, dp, graphs, shortest paths, trees, two pointers Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given a tree of n cities, meaning each city is connected in such a way that there is exactly one simple path between any two cities. Roads are undirected, and each road has a length of 1. The task is to...

Practice › Codeforces Solutions ›

Codeforces Alpha Round 20 (Codeforces format)

Codeforces Alpha Round 20 (Codeforces format) Type: Special | Problems: 3 | Verified: 3/3 | Rating range: 1700-2000 | Time: 4m 1s Problem Name Rating Tags Solve Time Verified A BerOS file system 1700 implementation 1m 20s ✓ B Equation 2000 math 1m 5s ✓ C Dijkstra? 1900 graphs, shortest-paths 1m 36s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 33 (Codeforces format) ›

CF 33D - Knights

CF 33D - Knights Rating: 2000 Tags: geometry, graphs, shortest paths, sortings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a map of Berland with several control points and circular fences. Each knight occupies a control point. Fences separate the kingdom into regions, and a knight must cross fences to move between control points. For multiple queries, we need to determine the minimum number of fences...

Practice › Codeforces Solutions › Codeforces Beta Round 29 (Div. 2, Codeforces format) ›

CF 29E - Quarrel

CF 29E - Quarrel Rating: 2400 Tags: graphs, shortest paths Solve time: 1m 16s Verified: no Solution Problem Understanding We are asked to route two people, Bob and Alex, across a town represented as an undirected graph with n crossroads and m roads. Bob starts at node 1 and wants to reach node n , while Alex starts at node n and wants to reach node 1. Both must travel...

Practice › Codeforces Solutions › Codeforces Beta Round 25 (Div. 2 Only) ›

CF 25C - Roads in Berland

CF 25C - Roads in Berland Rating: 1900 Tags: graphs, shortest paths Solve time: 58s Verified: yes Solution Problem Understanding We are given a map of n cities in Berland, where the shortest distances between all pairs are already known. Conceptually, this means the country is fully connected via some unknown set of roads, and the distance matrix is already the all-pairs shortest path result. The government plans to add...

Practice › Codeforces Solutions › Codeforces Beta Round 3 ›

CF 3A - Shortest path of the king

CF 3A - Shortest path of the king Rating: 1000 Tags: greedy, shortest paths Solve time: 4m 37s Verified: yes Problem Understanding We are asked to move a chess king from one square to another on a standard 8×8 board in the fewest number of moves. The king can move to any adjacent square in eight possible directions: vertically, horizontally, or diagonally. The input specifies the start and target squares...

Practice › Codeforces Solutions › Codeforces Beta Round 33 (Codeforces format) ›

CF 33B - String Problem

CF 33B - String Problem Rating: 1800 Tags: shortest paths Solve time: 7m 1s Verified: yes Solution Problem Understanding We are given two lowercase strings of the same length. We may repeatedly transform characters using directed conversion rules. A rule like a -> b with cost 5 means we can change one occurrence of a into b by paying 5 . The goal is not to convert one whole string...

Practice › Codeforces Solutions ›

Codeforces Beta Round 3

Codeforces Beta Round 3 Type: Beta | Problems: 4 | Verified: 4/4 | Rating range: 1000-2600 | Time: 14m 42s Problem Name Rating Tags Solve Time Verified A Shortest path of the king 1000 greedy, shortest-paths 4m 37s ✓ B Lorry 1900 greedy, sortings 4m 5s ✓ C Tic-tac-toe 1800 brute-force, games, implementation 4m 37s ✓ D Least Cost Bracket Sequence 2600 greedy 1m 23s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 35 (Div. 2) ›

CF 35C - Fire Again

CF 35C - Fire Again Rating: 1500 Tags: brute force, dfs and similar, shortest paths Solve time: 2m 10s Verified: yes Solution Problem Understanding We have a rectangular grid of trees. A fire starts simultaneously from several cells, and every minute it spreads to neighboring cells that share a side. The task is to find any cell whose burning time is as large as possible, meaning it catches fire later...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Finals ›

CF 97C - Winning Strategy

CF 97C - Winning Strategy Rating: 2400 Tags: binary search, graphs, math, shortest paths Solve time: 1m 44s Verified: yes Solution Problem Understanding Each year the university sends a team of exactly n students to the finals. Some of those students may already have participated once before, and the rest are newcomers. If exactly i members already have previous finals experience, the probability of winning a medal that year is...

Practice › Codeforces Solutions › Codeforces Beta Round 71 ›

CF 79D - Password

CF 79D - Password Rating: 2800 Tags: bitmasks, dp, shortest paths Solve time: 2m 11s Verified: yes Solution Problem Understanding We start with a row of n panels, all turned OFF. The target password is another configuration where exactly k specific positions must be ON and every other position must remain OFF. One operation chooses a segment of consecutive panels whose length belongs to the array a . Every panel...

Practice › Codeforces Solutions › Codeforces Beta Round 72 (Div. 1 Only) ›

CF 83C - Track

CF 83C - Track Rating: 2400 Tags: graphs, greedy, shortest paths Solve time: 2m 22s Verified: yes Solution Problem Understanding We have a rectangular grid. Each cell contains either a terrain type represented by a lowercase letter, the start cell S , or the target cell T . We may move in four directions between side-adjacent cells. Every move costs exactly one minute. The path must start at S and...

Practice › Codeforces Solutions ›

Codeforces Beta Round 72 (Div. 1 Only)

Codeforces Beta Round 72 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1300-2800 | Time: 9m 17s Problem Name Rating Tags Solve Time Verified A Magical Array 1300 math 1m 28s ✓ B Doctor 1800 binary-search, math, sortings 1m 37s ✓ C Track 2400 graphs, greedy, shortest-paths 2m 22s ✓ D Numbers 2400 dp, math, number-theory 2m 7s ✓ E Two Subsequences 2800...

Practice › Codeforces Solutions ›

Codeforces Beta Round 25 (Div. 2 Only)

Codeforces Beta Round 25 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2200 | Time: 6m 12s Problem Name Rating Tags Solve Time Verified A IQ test 1300 brute-force 1m 7s ✓ B Phone numbers 1100 implementation 1m 24s ✓ C Roads in Berland 1900 graphs, shortest-paths 58s ✓ D Roads not only in Berland 1900 dsu, graphs, trees 1m 15s ✓ E...

Practice › Codeforces Solutions › Codeforces Beta Round 37 ›

CF 37E - Trial for Chief

CF 37E - Trial for Chief Rating: 2600 Tags: graphs, greedy, shortest paths Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a rectangular slab divided into an $N \times M$ grid of squares. Each square is either black or white in the final design, which is provided as input. The slab initially starts entirely white. Every day, a pretender can repaint a connected region of squares...

Practice › Codeforces Solutions ›

Codeforces Beta Round 33 (Codeforces format)

Codeforces Beta Round 33 (Codeforces format) Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1200-2600 | Time: 18m 29s Problem Name Rating Tags Solve Time Verified A What is for dinner? 1200 greedy, implementation 3m 53s ✓ B String Problem 1800 shortest-paths 7m 1s ✓ C Wonderful Randomized Sum 1800 greedy 3m 6s ✓ D Knights 2000 geometry, graphs, shortest-paths 1m 32s ✓ E Helper 2600 -...

Practice › Codeforces Solutions ›

Codeforces Beta Round 35 (Div. 2)

Codeforces Beta Round 35 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2100 | Time: 7m 52s Problem Name Rating Tags Solve Time Verified A Shell Game 1000 implementation 1m 26s ✓ B Warehouse 1700 implementation 1m 21s ✓ C Fire Again 1500 brute-force, dfs-and-similar, shortest-paths 2m 10s ✓ D Animals 1700 dp, greedy 1m 14s ✓ E Parade 2100 data-structures, sortings 1m 41s...

Practice › Codeforces Solutions › Codeforces Alpha Round 20 (Codeforces format) ›

CF 20C - Dijkstra?

CF 20C - Dijkstra? Rating: 1900 Tags: graphs, shortest paths Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given an undirected weighted graph. Every edge connects two vertices and has a positive cost. The task is to start at vertex 1 , reach vertex n , and print one shortest path. If no route exists, we print -1 . The graph is large enough that we cannot...

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

CF 78E - Evacuation

CF 78E - Evacuation Rating: 2300 Tags: flows, graphs, shortest paths Solve time: 2m 34s Verified: yes Solution Problem Understanding We are given a laboratory grid of size n × n , representing a research station where some tiles are reactors and others are laboratories. One reactor is malfunctioning and will explode, causing toxic coolant to spread to neighboring labs. Each laboratory contains some number of scientists and some number...

Practice › Codeforces Solutions › Codeforces Beta Round 55 (Div. 2) ›

CF 59E - Shortest Path

CF 59E - Shortest Path Rating: 2000 Tags: graphs, shortest paths Solve time: 1m 18s Verified: yes Solution Problem Understanding We are asked to navigate a graph of cities connected by bidirectional roads, with a twist: certain sequences of three consecutive cities are forbidden due to superstition. Formally, there are n nodes and m edges, all unweighted, representing cities and roads. We start at city 1 and want to reach...

Practice › Codeforces Solutions › Codeforces Beta Round 53 ›

CF 57E - Chess

CF 57E - Chess Rating: 3000 Tags: math, shortest paths Solve time: 2m 3s Verified: yes Solution Problem Understanding We start on an infinite chessboard at square (0, 0) . A knight moves using the usual chess move, two cells in one direction and one in the perpendicular direction. Some squares are removed from the board, and the knight is never allowed to stand on them. The task is to...

Practice › Codeforces Solutions ›

Codeforces Beta Round 77 (Div. 1 Only)

Codeforces Beta Round 77 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1600-2500 | Time: 7m 52s Problem Name Rating Tags Solve Time Verified A Hockey 1600 implementation, strings 1m 15s ✓ B Lucky Numbers 1800 dp, greedy 1m 52s ✓ C Volleyball 1900 shortest-paths 1m 21s ✓ D Horse Races 2500 dp, math 2m ✓ E Lucky Country 2500 dp, dsu, graphs...

Practice › Codeforces Solutions › Codeforces Round 933 (Div. 3) ›

CF 1941G - Rudolf and Subway

CF 1941G - Rudolf and Subway Rating: 2000 Tags: constructive algorithms, dfs and similar, graphs, shortest paths Solve time: 1m 8s Verified: yes Solution Problem Understanding The problem describes a subway system as an undirected graph where each vertex is a station and each edge represents a direct connection between two stations. Every edge is labeled with a color representing the subway line it belongs to. All edges of the...

Practice › Codeforces Solutions › Codeforces Beta Round 57 (Div. 2) ›

CF 61D - Eternal Victory

CF 61D - Eternal Victory Rating: 1800 Tags: dfs and similar, graphs, greedy, shortest paths, trees Solve time: 1m 29s Verified: yes Solution Problem Understanding We are asked to find the minimum distance Shapur must travel to visit all cities at least once. The cities are connected in a tree structure, meaning there are exactly $n-1$ bidirectional roads and a unique path between any two cities. Shapur starts at city...

Practice › Codeforces Solutions › Codeforces Beta Round 67 (Div. 2) ›

CF 75E - Ship's Shortest Path

CF 75E - Ship's Shortest Path Rating: 2400 Tags: geometry, shortest paths Solve time: 2m 29s Verified: yes Solution Problem Understanding We are given two points in the plane, the ship's starting position and destination, together with a convex polygon representing an island. Moving through the sea costs 1 per unit distance. Moving through the interior of the island costs 2 per unit distance. Moving along the polygon boundary is...

Practice › Codeforces Solutions › Codeforces Beta Round 17 ›

CF 17B - Hierarchy

CF 17B - Hierarchy Rating: 1500 Tags: dfs and similar, dsu, greedy, shortest paths Solve time: 1m 34s Verified: yes Solution Problem Understanding We have employees and directed supervisor offers between them. An offer (a, b, c) means employee a is willing to supervise employee b for cost c . Qualifications are strictly decreasing along every offer, so q[a] > q[b] . The final hierarchy must be a rooted tree....

#shortest-paths

10.8 Finding Shortest Paths in Directed Acyclic Graphs

10.7 Computing All-Pairs Shortest Paths with Floyd-Warshall

10.2 Finding Shortest Paths with BFS

10.20 Choosing the Right Shortest-Path Algorithm

10.25 Debugging and Optimizing Shortest-Path Code

10.10 Solving 0-1 Shortest Path Problems with 0-1 BFS

10.23 Common Shortest-Path Patterns and Interview Problems

10.17 Finding K Shortest Paths

10.3 Solving Nonnegative Weighted Shortest Paths with Dijkstra's Algorithm

10.24 Testing Shortest-Path Implementations

10.5 Detecting Negative Edges with Bellman-Ford

10.6 Detecting Negative Cycles with Bellman-Ford

10.12 Accelerating Searches with Bidirectional Search

10.14 Using Distance Labels and Relaxation Correctly

10.21 Proving Correctness of Shortest-Path Algorithms

10.22 Analyzing Complexity of Shortest-Path Algorithms

10.13 Reconstructing Shortest Paths

10.18 Solving Shortest Paths on Grids

10.9 Computing Multi-Source Shortest Paths

10.15 Using Potentials to Reweight Graphs

10.19 Modeling State-Space Problems as Shortest Paths

10.16 Solving Sparse All-Pairs Shortest Paths with Johnson's Algorithm

10.4 Implementing Dijkstra with Priority Queue Variants

10.11 Accelerating Search with A

10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search

Chapter 10. Shortest Paths

CF 1967D - Long Way to be Non-decreasing

CF 1948C - Arrow Path

CF 1955H - The Most Reckless Defense

Educational Codeforces Round 163 (Rated for Div. 2)

CF 1975D - Paint the Tree

Codeforces Round 257 (Div. 1)

CF 472D - Design Tutorial: Inverse the Problem

Codeforces Round 270

CF 464E - The Classic Problem

CF 461E - Appleman and a Game

CF 449B - Jzzhu and Cities

CF 238E - Meeting Her

CF 229B - Planets

CF 173B - Chamber of Secrets

Croc Champ 2012 - Round 1

CF 196E - Opening Portals

Codeforces Round 179 (Div. 1)

CF 187B - AlgoRace

CF 175F - Gnomes of Might and Magic

Codeforces Round 182 (Div. 1)

CF 253C - Text Editor

CF 295B - Greg and Graph

CF 144D - Missile Silos

CF 311C - Fetch the Treasure

Codeforces Round 119 (Div. 1)

Codeforces Round 117 (Div. 2)

CF 241E - Flights

CF 242C - King's Path

CF 266B - Queue at the School

CF 254D - Rats

CF 182A - Battlefield

Codeforces Round 130 (Div. 2)

Codeforces Round 163 (Div. 2)

Codeforces Round 103 (Div. 2)

CF 301B - Yaroslav and Time

CF 141D - Take-off Ramps

Bayan 2012-2013 Elimination Round (ACM ICPC Rules, English statements)

CF 416E - President's Path

CF 232C - Doe Graphs

CF 295C - Greg and Friends

CF 266D - BerDonalds

CF 329B - Biridian Forest

CF 317E - Princess and Her Shadow

Codeforces Round 192 (Div. 1)

Codeforces Round 142 (Div. 1)

CF 208C - Police Station

CF 95C - Volleyball

CF 14D - Two Paths

Codeforces Alpha Round 20 (Codeforces format)

CF 33D - Knights

CF 29E - Quarrel

CF 25C - Roads in Berland

CF 3A - Shortest path of the king