HBC24708答题人的愤怒[USACO 2011 Mar B]Pathfinding题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

Bessie is stranded on a deserted arctic island and wants to determine all the paths she might take to return to her pasture. She has tested her boat and knows she can travel from one island to another island in 1 unit of time if a route with proper currents connects the pair. She has experimented to create a map of the ocean with valid single-hop routes between each pair of the N (1 <= N <= 100) islands, conveniently numbered 1..N. The routes are one-way unidirectional), owing to the way the currents push her boat in the ocean. It's possible that a pair of islands is connected by two routes that use different currents and thus provide a bidirectional connection. The map takes care to avoid specifying that a route exists between an island and itself. Given her starting location M (1 <= M <= N) and a representation of the map, help Bessie determine which islands are one 'hop' away, two 'hops' away, and so on. If Bessie can take multiple different paths to an island, consider only the path with the shortest distance. By way of example, below are N=4 islands with connectivity as shown (for this example, M=1): start--> 1-------->2 | | | | V V 4<--------3 Bessie can visit island 1 in time 0 (since M=1), islands 2 and 4 at time 1, and island 3 at time 2. The input for this task is a matrix C where the element at row r, column c is named C_rc (0 <= C_rc <= 1) and, if it has the value 1, means "Currents enable Bessie to travel directly from island r to island c in one time unit". Row C_r has N elements, respectively C_r1..C_rN, each one of which is 0 or 1.

想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。

标签： HBC24708答题人的愤怒[USACO 2011 Mar B]Pathfinding题解