Connection Status:
Competition Arena > NegativeGraphDiv1

NegativeGraphDiv1

SRM 626 · 2013-12-22 · by lg5293

SRM 626 · 2013-12-22 · by lg5293 · Dynamic Programming, Graph Theory
Class Name: NegativeGraphDiv1
Return Type: long
Method Name: findMin
Arg Types: (int, vector<int>, vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Nancy has a directed graph with N vertices and E edges. The vertices are numbered 1 through N. Each edge of the graph has a positive integer weight. This graph is described by three int[]s with E elements each: from, to, and weight. For each valid i, the graph contains an edge from from[i] to to[i], and its weight is weight[i]. Note that Nancy's graph may contain multiple edges with the same start and end. It may also contain self-loops.

Nancy is currently standing in the vertex 1. She can reach other vertices by moving along the edges. The cost of using an edge is equal to its weight. Nancy's goal is to reach the vertex N and to minimize the total cost of doing so.

Nancy has a special power she can use to make her travels cheaper. Whenever she traverses an edge, she can use that special power to make the weight of that edge temporarily negative. You are given an int charges: the number of times Nancy can use her special power. Each use of the special power only works for one traversal of an edge. Nancy can traverse each edge arbitrarily many times. Each time she traverses an edge, she may use her special power, if she still has some charges left.

Compute and return the minimal total cost of Nancy's journey.

Constraints

  • N will be between 1 and 50, inclusive.
  • E will be between 1 and 2500, inclusive.
  • from, to, weight will each contain exactly E elements.
  • from and to will only contain numbers between 1 and N, inclusive.
  • There will be a path from node 1 to node N.
  • weight will contain numbers between 0 and 100,000, inclusive.
  • charges will be between 0 and 1,000,000,000, inclusive.
Examples
0)
3
{1,1,2,2,3,3}
{2,3,1,3,1,2}
{1,5,1,10,1,1}
1
Returns: -9

The optimal path for Nancy is 1->2->3, and using her single charge on the last edge.

1)
1
{1}
{1}
{100}
100000
Returns: -10000000

The graph may contain self-loops. Here, the optimal solution is that Nancy uses the self-loop 100,000 times, each time using her special power to change its cost from 100 to -100.

2)
2
{1,1,2}
{2,2,1}
{6,1,4}
2
Returns: -9

There can be multiple edges between vertices.

3)
2
{1}
{2}
{98765}
1000000000
Returns: -98765

Nancy may not be able to use all her charges.

4)
4
{1,2,3,4}
{2,3,4,1}
{1,10,1,1}
8593423
Returns: -60153962

Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NegativeGraphDiv1 with a public method long long findMin(int N, vector<int> from, vector<int> to, vector<int> weight, int charges) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous