JOIN
Get Time

   Problem Statement  

 Problem Statement for MaliciousPath

Problem Statement

    

Alice and Bob are playing a game on a graph. The graph has int N nodes, and M directed edges. The graph is described by the int[] from,to,cost. The i-th edge is a directed edge that connects node from[i] to node to[i] and has weight cost[i]. This graph may have self loops or multiple edges. Each node has at least one outgoing edge.

Alice is currently at at node 0. She wishes to travel to node N-1. Bob initially has K tokens. At each node along Alice's path, she will first announce which outgoing edge she intends to traverse. If Bob wishes and if he still has a token, he may spend one token and choose a different outgoing edge from Alice's current node. Alice will then be forced to travel along the edge chosen by Bob and incur the cost of this edge. If Bob does not use a token, Alice travels along the edge she announced, incurring the cost of the edge. Alice knows how many tokens Bob has remaining at all times. The game ends when Alice reaches node N-1, or she traverses an edge 1,000,000,000 times without reaching the node N-1.

Alice wishes to minimize her travel time. Bob will use his tokens in such a way that Alice cannot reach node N-1 if it is possible. Otherwise, he will use them to maximize the total cost that Alice incurs before reaching node N-1, and Alice will always choose an option to minimize the total cost. If it is not possible for Alice to make it to node N-1, return -1. Otherwise, compute and return the minimum time that Alice can guarantee to reach the node N-1.

 

Definition

    
Class:MaliciousPath
Method:minPath
Parameters:int, int, int[], int[], int[]
Returns:long
Method signature:long minPath(int N, int K, int[] from, int[] to, int[] cost)
(be sure your method is public)
    
 

Constraints

-N will be between 2 and 1,000, inclusive.
-from,to,cost will each contain between 1 and 2,500 elements, inclusive.
-from,to,cost will contain the same number of elements.
-Each element of from,to will be between 0 and N-1, inclusive.
-Each element of cost will be between 0 and 1,000,000, inclusive.
-Each integer between 0 and N-1, inclusive, will appear at least once in the array from.
-K will be between 0 and 1,000, inclusive.
 

Examples

0)
    
3
1000
{0,1,1,2}
{1,0,2,2}
{3,2,1,1}
Returns: 5004

When Alice is at node 0, she will attempt to travel to node 1 using the first edge. Bob will do nothing. When Alice is at node 1, she will attempt to travel to node 2 using the third edge. If Bob has a token, Bob will make her go back to node 0 instead using the second edge. Thus, Alice has to travel the cycle 0->1->0 1000 times before she can successfully make it to node 2. This will yield a total cost of 5004.

1)
    
4
1
{0,0,1,1,1,2,2,3}
{1,3,0,2,3,2,1,3}
{0,100,103,0,0,34,102,33}
Returns: 100

In this case, Alice's optimal strategy is to attempt to go to node 3 directly from node 0. Bob's optimal response will be not use a token, allowing Alice to reach node 3.

2)
    
10
5
{0,0,1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9}
{1,1,2,2,3,3,4,4,5,5,4,6,6,7,7,8,8,9,9,9,9}
{2,10,10,1,2,10,10,1,2,10,100,10,2,1,10,10,2,1,10,10,1}
Returns: 514
3)
    
50
200
{0,13,8,17,3,8,4,21,11,20,2,18,21,2,4,9,17,0,14,10,15,18,1,22,10,14,
19,24,5,5,12,7,7,16,19,13,20,15,23,6,23,9,3,6,16,11,22,24,12,1,25,25,
26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,
37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,
49,49,37,9,14,0,33,20,46,26,12,11,2,7,34,19,37,5,2,17,41,16,34,13,18,
35,6,14,16,25,9,10,5,10,7,36,45,3,6,22,32,28,45,40,16,36,28,16,34,1,
9,19,18,6,15,29,12,5,44,33,49,14,40,1,30,21,37,49,1,44,42,6,38,1,31,
40,37,34,35,6,43,29,41,48,17,4,38,26,4,46,43,6,27,30,0,16,40,33,0,42,
41,10,33,47,11,37,49,25,36,20,47,12,28,17,11,17,26,26,37,34,27,17,8,
2,13,43,36,28,1,23,29,40,18,22,0,7,30,23,3,39,5,23,28,38,44,19,43,15,
16,43,5,27,24,25,7,16,38,33,33,1,9,25,47,0,31,30,29,4,36,49,26,6,39,
40,28,39,48,26,2,15,41,42,32,0,35,34,28,30,40,3,33,16,15,41,45,12,33,
35,16,47,34,23}
{41,42,17,0,2,7,28,32,31,33,6,42,11,13,7,40,47,21,4,6,19,15,4,18,30,25,
2,10,30,34,1,47,35,23,3,0,9,25,42,21,4,6,47,32,5,40,5,0,8,49,16,29,8,
11,42,33,35,26,27,43,35,6,14,13,44,25,13,42,2,26,17,3,40,31,18,12,24,
37,0,37,15,44,35,40,10,1,35,47,36,33,2,39,23,28,32,0,6,21,33,41,0,19,
16,29,35,16,44,6,18,17,2,46,41,11,27,5,44,1,48,15,43,8,41,33,16,11,45,
47,19,41,14,41,8,24,13,3,44,41,42,30,31,44,21,14,43,48,0,6,25,38,36,14,
36,22,43,15,20,19,37,25,17,44,17,46,8,25,33,19,42,40,42,24,15,31,34,8,
41,25,20,29,2,5,43,28,33,40,31,27,6,21,9,35,8,8,26,13,11,31,4,4,30,34,
35,1,15,11,10,24,15,24,23,16,24,32,9,1,6,17,48,6,35,19,12,5,21,23,25,9,
17,47,19,23,22,35,19,5,1,10,9,41,11,45,0,23,0,11,39,0,17,2,18,4,17,24,0,
10,19,4,36,22,42,18,13,48,27,11,19,28,31,39,32,48,2,26,38,43,38,49,34,
37,11,9,11,14,12,9,37,0,22,14,15,0,8,23,7,43,5,8,16,47}
{494,848305,3326,6008,223,2,6,673,152335,25,713909,42842,122,9941,361853,
35,20157,1098,41,83693,365851,43843,622,591230,7722,2489,7,861622,21272,
169,1153,3,7,3,577031,24522,5,241,757900,11036,8892,199,7,2,1,453031,115,
13,125,67,35,91,33427,14,106,203749,5,1804,4543,23,1,281,441212,18,3,
11629,233,388188,10,701,76170,763,875,11606,44972,6449,37409,83516,5912,
6,705899,26759,253,580531,14215,21916,884775,30,678,5940,17,480830,8,
61,218613,683352,4,557589,2619,3658,221515,15825,163577,25,9,1,4,13,2,88,
147,110163,18118,2,15429,211872,24,1,188382,12500,2348,190,4279,40,8428,
56325,933152,231523,9454,21,4855,96168,1722,329515,77,1,3,3518,10926,
12172,4,71,181976,1318,9,5086,905,108490,80164,2,10236,197,1880,17420,
614650,372457,13918,36,17,167,6,254127,512,15,341436,1,186,96,7,3,42,4,
3,4,492598,18523,172302,1,421535,390382,2952,6228,871,505372,131266,5,
743902,11,34,657,4717,3196,259,192504,229,6786,28,44364,21123,8,166781,
885021,2,828,497,376,24707,52,1,1659,19402,27261,82,473,443,1089,586,20,
7,239277,27132,4681,761,10644,17798,1,820306,13330,19,293167,2,4,89279,
14,1,9,18023,1165,495221,32304,538,178613,1,4764,32767,114,103,1,302,428,
92,927352,22270,2646,3599,6,16362,3,4,280286,338,652,2,347022,23,323084,
3338,46,58,1263,93,46992,19112,1,19499,33,807600,20296,16803,911294,3151,
1,793,1,1,504,62209,1397,52726,3650,54,3630,358480,178,394,28,137436,52764,
1209,1599}
Returns: 121213509
4)
    
20
1000
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,18}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,0}
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000}
Returns: 19019000000
5)
    
2
0
{0,1}
{0,1}
{5,4}
Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 652 Round 1 - Division I, Level Two