Connection Status:
Competition Arena > ShortestPathWithMagic

ShortestPathWithMagic

SRM 675 · 2015-11-03 · by cgy4ever

SRM 675 · 2015-11-03 · by cgy4ever · Graph Theory
Class Name: ShortestPathWithMagic
Return Type: double
Method Name: getTime
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

There are n cities, numbered from 0 to n-1. It is possible to travel directly between any two cities. Different pairs of cities may require different travel times. You are given the travel times as a String[] dist with n elements, each consisting of n digits. The digit dist[i][j] represents the time needed to travel between cities i and j in either direction.

You are also given an int k. You have k magic potions. The potion makes you twice as fast as you normally are. Each time you travel (directly) from some city to some other city, you may take one of the potions. If you do, that travel will only take half of what it normally would. You are not allowed to take more than one potion at the same time. You are not required to drink all potions you have.

Compute and return the smallest amount of time in which you can travel from city 0 to city 1.

Notes

  • The travel times given in dist don't have to satisfy the triangle inequality.
  • Your return value must have a relative or absolute error less than 1e-9

Constraints

  • dist will contain between 2 and 50 elements, inclusive.
  • Each string in dist will contain exactly |dist| characters.
  • Each character in dist will be between '0' and '9', inclusive.
  • For any valid i and j: dist[i][j] = dist[j][i].
  • For any valid i: dist[i][i] = 0.
  • k will be between 0 and 50, inclusive.
Examples
0)
{"094",
 "904",
 "440"}
1
Returns: 4.5

According to dist, you need: 9 units of time to travel between cities 0 and 1 4 units of time to travel between cities 0 and 2 4 units of time to travel between cities 1 and 2 You have a single magic potion. The optimal solution is to drink the potion and to travel directly from city 0 to city 1. This trip will take 9/2 = 4.5 units of time.

1)
{"094",
 "904",
 "440"}
2
Returns: 4.0

The normal travel times are the same as in Example 0, but now you have two magic potions. This changes the optimal solution. Now it is better to travel from 0 to 2 and then from 2 to 1. For each segment of your trip you will drink one of the potions. Thus, each segment will only take 4/2 = 2 units of time.

2)
{"094",
 "904",
 "440"}
50
Returns: 4.0

You are not allowed to use more than one potion at the same time. The optimal solution remains the same as in Example 1, only now you will still have 48 magic potions when you reach city 1.

3)
{"094",
 "904",
 "440"}
0
Returns: 8.0
4)
{"076237",
 "708937",
 "680641",
 "296059",
 "334508",
 "771980"}
1
Returns: 3.5

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

Coding Area

Language: C++17 · define a public class ShortestPathWithMagic with a public method double getTime(vector<string> dist, int k) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous