Connection Status:
Competition Arena > FoxAirline

FoxAirline

2015 TCO Semifinal · 2015-04-08 · by cgy4ever

2015 TCO Semifinal · 2015-04-08 · by cgy4ever · Dynamic Programming, Graph Theory
Class Name: FoxAirline
Return Type: int
Method Name: minimalCost
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel has an airline company: Fox Airline. The company currently offers several one-directional flights.

There are n airports in the region serviced by Fox Airline. The airports are numbered 0 through n-1. You are given the int n. You are also given three int[]s: a, b, and c. These contain information about the flights offered by Fox Airline: For each valid i there is a flight from the airport a[i] to the airport b[i]. The cost of operating this flight is c[i] dollars per year.

Fox Ciel would now like to cut some costs while making sure she allows her customers to travel everywhere. More precisely, Ciel is going to choose some of the flights she currently operates, and cancel all others. She has two goals:
  • For any two airports x and y there must be a way to travel from x to y by only using chosen flights.
  • Given the above rule, the total cost of chosen flights (in dollars per year) must be as small as possible.
If Ciel can achieve her goal, return the smallest possible total cost of the chosen flights. If there is no valid way to choose the flights, return -1.

Constraints

  • n will be between 1 and 12, inclusive.
  • a will contain between 0 and n*(n-1) elements, inclusive.
  • a, b and c will contain same number of elements.
  • Each element in a will be between 0 and n-1, inclusive.
  • Each element in b will be between 0 and n-1, inclusive.
  • Each element in c will be between 1 and 100,000, inclusive.
  • For each valid i, a[i] will be different from b[i].
  • For each valid and different i and j, the ordered pair (a[i], b[i]) will be different from (a[j], b[j]).

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
3
{0,0,1,2,1,2}
{1,2,0,0,2,1}
{1,1,1,1,10,10}
Returns: 4

It is possible to only keep three flights, but that is not the cheapest solution. Instead, we should choose the first four flights. The total cost is only 1+1+1+1 = 4, and it is still possible to travel from any airport to any other airport.

1)
3
{0,1,0,1}
{1,0,2,2}
{1,2,3,4}
Returns: -1

There is no valid solution, even if we choose all flights, we can't get from city 2 to city 0.

2)
4
{0,1,2,3}
{1,2,3,0}
{10,20,30,40}
Returns: 100

We need to choose all flights.

3)
5
{0,1,2,3}
{1,2,3,0}
{10,20,30,40}
Returns: -1
4)
12
{5,7,1,9,5,7,3,1,11,8,1,10,2,7,8,7,2,11,6,4,6,9,4,4,3,7,1,0,4,
10,0,6,6,8,9,0,6,6,11,10,5,5,9,0,11,3,5,0,9,7,7,5,11,8,1,8,3,
4,7,4,3,8,3,4,3,8,10,0,11,11,0,6,4,0,1,6,0,3,0,9,11,2,1,3,8,1,
2,4,11,1,7,5,5,9,9,7,5,2,4,8,2,10,3,9,5,0,11,3,2,6,6,1,6,4,2,
9,10,11,10,2,7,8,8,2,10,2,10,9,1,5,10,10}
{0,3,2,3,3,11,0,4,1,0,9,3,1,8,5,9,5,2,11,1,1,2,7,9,4,2,0,10,0,
0,7,2,9,4,4,9,7,8,8,8,9,2,11,11,10,10,4,6,5,10,6,10,0,2,3,10,
1,3,0,2,2,6,5,11,6,3,5,8,6,3,2,4,10,5,5,5,4,9,3,8,7,4,7,11,7,
10,11,8,4,8,4,11,8,7,10,5,6,7,5,1,9,2,8,0,1,1,5,7,0,3,0,11,10,
6,8,6,1,9,9,6,1,9,11,3,6,10,7,1,6,7,11,4}
{25984,89713,21689,14734,59359,53691,32670,17291,10665,7734,
78780,41871,51780,29833,83512,65961,1102,19919,82940,78302,
33977,93139,34297,40731,43477,27993,57723,12152,3980,70786,
35521,70833,64827,59029,43895,90715,48944,83551,24446,16475,
87602,93225,97981,94059,22358,99691,62932,90503,97309,87273,
52990,70178,95405,60529,54542,18236,3626,390,7246,93273,91896,
95133,94136,17526,40131,66971,3155,80877,27302,35933,20726,
36474,60672,64932,97730,17345,80773,3805,33962,10994,41796,
94727,81676,52518,36032,67199,99638,79108,39564,48423,20062,
43372,78076,70519,6529,80526,64653,68090,49366,82926,96800,
46972,3187,21071,40295,59157,98610,21594,64406,26409,54502,
32364,42991,32988,31586,90087,48361,86876,32023,64035,36642,
25221,35100,6541,61459,22219,93856,34767,87048,90635,29986,
21603}
Returns: 189591

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 FoxAirline with a public method int minimalCost(int n, vector<int> a, vector<int> b, vector<int> c) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous