Under construction

Still being built. Things may change

Card Captor Hanbyul

Time limit1sMemory limit1024 MB

Summary
Find the shortest route from vertex 1 that visits all N card vertices in a directed graph, where a vertex can be entered only if its power is at most the cards held.
Level

Medium6 of 10

Topics
Graph, Shortest path, Dynamic programming
Solved
No attempts yet

Problem

One day, Hanbyul, who was living an ordinary life, became a magical girl. Growing stronger as a magical girl, Hanbyul decided to defeat the executives of the evil organization "Bogy." However, since Hanbyul is not skilled at magic, Hanbyul first decided to collect all NN "Stardust Cards," which allow anyone with magic power to use magic.

Hanbyul's region can be represented as a directed graph with VV vertices and EE edges. The vertices are numbered from 11 to VV, and each edge has a fixed length. Hanbyul starts at vertex 11. The NN "Stardust Cards" are placed one each on NN target vertices. Hanbyul gets one card the first time Hanbyul visits each target vertex. After learning that Hanbyul collects "Stardust Cards," Bogy placed one executive on every vertex. To avoid interference from Bogy, Hanbyul must only travel through vertices where the executive's power is less than or equal to the number of cards Hanbyul holds. If Hanbyul holds LL cards and wants to move to a vertex, the executive's power there must be at most LL, regardless of whether a card is on that vertex.

Find the minimum travel distance of Hanbyul's route so that Hanbyul can collect the cards quickly. Hanbyul stops moving immediately after collecting all NN "Stardust Cards."

Examples3

  1. Example 1

    Input
    2 6 6
0 0 0 0 0 1
2 6
1 2 1
2 3 10
3 4 100
4 5 1000
2 5 10000
5 6 100000
    Expected output
    101111

  2. Example 2

    Input
    3 6 6
0 0 2 1 1 2
2 5 6
1 2 1
2 3 10
3 5 100
2 4 1000
4 5 10000
5 6 100000
    Expected output
    111001

  3. Example 3

    Input
    2 4 3
0 1 0 0
2 4
1 2 1
2 3 10
3 4 100
    Expected output
    -1