DiscountedShortestPaths

SRM 795 · 2020-12-11 · by jy_25

SRM 795 · 2020-12-11 · by jy_25 · Graph Theory, Greedy

Show categories

Class Name: DiscountedShortestPaths

Return Type: long

Method Name: minimumCostSum

Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)

Problem Statement

Please note the unusual time and memory limits in this problem: 4 seconds, 48 MB.

There are n cities numbered 0 to n-1. Some pairs of cities are connected by flights. All flights are bidirectional. The network is connected: it is possible to travel between any two cities (directly or indirectly).

You are given n and the list of flights: the int[]s a, b, c. For each valid i, there is a bidirectional flight that connects cities a[i] and b[i] and has a cost c[i] in either direction.

You have some discount coupons, each with some value. These values are given in the int[] d. For each flight you take you can only use at most one discount coupon. Also, each discount coupon can only be used once. If you have a flight with cost C and you use a discount coupon with value D, the new cost of the flight is what remains: max(0, C-D).

For each pair of cities s < t, consider the following problem: Suppose we want to travel from s to t with the given flight costs and the given discount coupons. What is the minimum total cost f(s, t) of our trip?

Calculate and return the sum of all f(s, t).

Notes

Each of the values f(s, t) is defined as an answer to a separate problem. Those problems don't influence each other. In particular, the optimal solutions for different f(s, t) may use overlapping sets of discount coupons.

Constraints

n will be between 2 and 20, inclusive.
a will have between n - 1 and n(n - 1) / 2 elements, inclusive.
a, b and c will have the same number of elements.
d will have between 0 and 20 elements, inclusive.
Between any two cities, there will be a direct or indirect path using flights.
For each valid i, a[i] and b[i] will be between 0 and n - 1, inclusive.
For each valid i, c[i] will be between 1 and 10 9 , inclusive.
For each valid i, d[i] will be between 1 and 10 9 , inclusive.
There will be no flight from a city to itself, and no two flights will connect the same pair of cities.

Examples

2
{0}
{1}
{10}
{5, 6}
Returns: 4

The travel cost f(0, 1) is 10 - 6 = 4. (Use the only flight and the bigger discount coupon.)

3
{0, 1, 2}
{1, 2, 0}
{3, 3, 7}
{2, 2, 2}
Returns: 4

f(0, 1) = 1 (use the flight between 0 and 1 and apply a discount coupon). f(1, 2) = 1 (use the flight between 1 and 2 and apply a discount coupon). f(0, 2) = 2 (go from 0 to 1, then from 1 to 2, using a discount coupon on both flights).

3
{0, 1, 2}
{1, 2, 0}
{3, 3, 7}
{1, 6, 1}
Returns: 1

10
{0, 1, 2, 3, 4, 5, 6, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}
{}
Returns: 165000000000

20
{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19}
{0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
{342339783, 134014197, 131410417, 956181377, 377410677, 576074728, 242317379, 641576577, 586475624, 639927301, 687510875, 814212059, 966868629, 13086683, 472198269, 357051697, 179156235, 19816458, 302960218, 812324363, 555429458, 710101054, 567864475, 36037197, 494155298, 481391793, 775993324, 711240135, 596920151, 252203570, 24761902, 499387611, 961552077, 516503148, 304983353, 297482880, 855639443, 15664215, 454088112, 380890354, 925952158, 35010576, 116251788, 220920930, 153765401, 563876016, 887988340, 164083454, 180842592, 994779025, 297211679, 770919204, 336811870, 341905988, 46978541, 21970617, 913860802, 538543051, 589865772, 252872101, 898558117, 830930865, 641752356, 397531149, 670171272, 988665706, 304085141, 890403701, 109357458, 441065198, 140367809, 564837873, 665489630, 975181855, 755956256, 747802593, 999883266, 959415947, 797991910, 842568293, 92436661, 898536952, 297957926, 54170420, 760949816, 213099495, 492695181, 383164365, 761179059, 248746122, 305303554, 745504526, 382968984, 158195335, 923869280, 56247977, 227397129, 938688492, 436760863, 947808276, 502185561, 471076834, 846618654, 127918225, 470105971, 649313049, 34708362, 457159112, 493372385, 743693296, 956305608, 773363110, 384122500, 532382479, 758128728, 247022453, 782109706, 524683171, 377436881, 688739474, 185737744, 294197958, 751690120, 254725227, 325907285, 175772031, 769671003, 521847843, 478086435, 849210942, 878108091, 737081919, 106774499, 525658942, 86698606, 177399264, 334211239, 745067632, 773964970, 237156732, 821433926, 91918595, 471661599, 120094799, 803951320, 974566764, 117758882, 414461391, 272953112, 769287364, 146691394, 850329567, 194941189, 669067964, 974320213, 404076381, 866876515, 294621175, 952165615, 397145392, 417702490, 793472278, 855455908, 211967495, 410414829, 348491190, 213389881, 250808404, 461805194, 541841607, 994020067, 349946785, 441432962, 507776364, 146652532, 635581132, 166782810, 142046953, 797529790, 48481955, 561621786, 809244662, 43754023, 507744324, 96108008, 610252310, 500038802, 907506094, 16780461, 989417009}
{17737629, 41586794, 34203579, 23195275, 5264301, 29783570, 20324690, 13257233, 28959787, 2445770, 36310512, 27519924, 11507304, 11979573, 30248027, 27919050, 36479088, 8261802, 45899076}
Returns: 14803349075

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

Coding Area

Language: C++17 · define a public class DiscountedShortestPaths with a public method long long minimumCostSum(int n, vector<int> a, vector<int> b, vector<int> c, vector<int> d) · 59 test cases · 2 s / 256 MB per case