Evacuation plan

Description

Discuss (14 comments)
This puzzle is a tribute to all the people who suffered from the earthquake in Japan. The goal of this puzzle is, given a network of road and locations, to determine the maximum number of people that can be evacuated.

The people must be evacuated from evacuation points to rescue points. The list of road and the number of people they can carry per hour is provided.

Input Specifications

Your program must accept one and only one command line argument: the input file. The input file is formatted as follows:
  1. the first line contains 4 integers n r s t
    • n is the number of locations (each location is given by a number from 0 to n-1)
    • r is the number of roads
    • s is the number of locations to be evacuated from (evacuation points)
    • t is the number of locations where people must be evacuated to (rescue points)
  2. the second line contains s integers giving the locations of the evacuation points
  3. the third line contains t integers giving the locations of the rescue points
  4. the r following lines contain to the road definitions. Each road is defined by 3 integers l1 l2 width
    where l1 and l2 are the locations connected by the road (roads are one-way) and width is the number of people per hour that can fit on the road
Example:
5 5 1 2
0
3 4
0 1 10
0 2 5
1 2 4
1 3 5
2 4 10

Output Specifications

The output of your program must be printed to the standard output.
The output should contain only 1 line, giving the maximal number of people that can be evacuated per hour.

For the previous example, the expected answer is:
14
© CoderCharts - All Rights Reserved
Type Puzzle Pass 161 Fail 198
Scoring Language Level Medium Points 900
Tags maximization, optimization, path search, recursion

Source code editor

Unit Tests

Name CPU Unit Memory Unit

Neighborhood

This test has 10 locations (2 evacuation points, 3 rescue areas) and 80 roads
1s
250 MB

Village

This test has 100 locations (1 evacuation point, 10 rescue areas) and 800 roads
1s
500 MB

City

This test has 100 locations (2 evacuation points, 20 rescue areas) and 8000 roads
1s
500 MB

Region

This test has 500 locations (50 evacuation points, 10 rescue areas) and 1000 roads
1s
500 MB

Country

This test has 1000 locations (10 evacuation points, 100 rescue areas) and 2000 roads
1s
1000 MB

Continent

This test has 1000 locations (3 evacuation points, 40 rescue areas) and 15000 roads
3s
1000 MB

Confirm that you want to switch languages
Your current edits will be lost.

Confirm that you wish to load a previous submission
Your current edits will be lost.