Canadian Computing Competition: 2018 Stage 1, Senior #5
A long time ago in a galaxy far, far away, there are planets numbered from
to
. Each planet has
cities numbered from
to
. Let city
of planet
be denoted as
.
There are two-way flights in the galaxy. For every planet
, there are
flights numbered from
to
. Flight
connects cities
and
and costs
energy daily to maintain.
There are two-way portals in the galaxy. For all cities with number
, there are
two-way portals numbered from
to
. Portal
connects cities
and
and costs
energy daily to maintain.
It is possible to travel between any two cities in the galaxy using only flights and/or portals.
Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.
What is the maximum sum of energy that can be saved daily?
Input Specification
The first line contains four space-separated integers ,
,
,
.
Then lines follow; the
-th one contains three space-separated integers
,
,
.
Then lines follow; the
-th one contains three space-separated integers
,
,
.
It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.
For of the
available marks,
,
for all
, and
for all
.
For an additional of the
available marks,
.
For an additional of the
available marks,
.
Output Specification
Output a single integer, the maximum sum of energy that can be saved daily.
Sample Input 1
2 2 1 2
1 2 1
2 1 1
2 1 1
Sample Output 1
3
Sample Input 2
2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5
Sample Output 2
41
Explanation for Sample Output 2
One possible way is to shut down the flights between cities and
,
and
,
and
,
and
,
and
, and shut down the portal between cities
and
for total energy savings of
.
Comments