$30.00

Category: CS 2010

Description

5/5 - (6 votes)

Story

Being a hemophilic, your lecturer Ket Fah will sometimes (hopefully not often) suffer from episodes of spontaneous

bleeding (bleeding without trauma). This usually occur in the joint areas and the bleeding must be quickly arrested or

it will become a big problem, hurt a lot and take a long time to recover. So when a bleeding episode happens, he will

usually need to rush to the hospital as fast as possible to have an injection that will quickly stop the bleeding.

The Actual Problem Description

Given a map of Singapore (as a directed weighted graph), estimated time

1

to travel through Singapore roads (as

nonnegative integer weights of the corresponding directed edges in minutes, with value not more than 1000), Ket

Fah’s current position s, the chosen hospital t, determine the shortest path to go from Ket Fah’s current position s to

the hospital t that uses no more than k junctions and report the shortest path weight: The sum of edge weights along

the shortest path. Ket Fah will call for a taxi or his brother will drive him and both will take this shortest path. It is

guaranteed that s and t are two vertices in the given directed weighted graph. There will be Q queries with varying s,

t, and k on the same given graph. If somehow there is no path from vertex s to vertex t that uses no more than k

junctions in the given graph, output ‐1.

Ket Fah needs the shortest path/quickest way that is also the safest

2

(no more than k junctions).

The skeleton program Bleeding.java (click to view) that can handle all input/output details is already written for you.

You just need to implement one (or more

4

) method(s)/function(s):

int Query(int s, int t, int k)

Query the Adjacency List data structure that is already implemented in the skeleton program where the

weight (in minutes) of each road (edge) is stored in the Adjacency List itself, and return the required answer.

Search search for… in NUS Websites

NUS WebMail IVLE LIBRARY MAPS

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2916 2/4

Now, let’s go back to the problem. For example, suppose Singapore

3 a directed weighted graph as shown below (all

edges are directed; notice that the pair of directed edges 0→2 (weight 9) and 2→0 (weight 1) that connects vertex 0

and vertex 2 can have different edge weights):

A sample Singapore map; Create and view this directed weighted graph at VisuAlgo

Query(0, 3, 4): If Ket Fah’s current position is at vertex s=0, the chosen hospital is at vertex t=3, and we can use

up to k=4 junctions, then the quickest way is this path: 0 → 1 → 2 → 3 with total estimated traveling time of: 2+3+7 =

12 minutes.

The shortest path from s=0 to t=3 with no more than k=4 junctions in this sample Singapore map

Query(1, 0, 4): If Ket Fah’s current position is at vertex s=1, the chosen hospital is at vertex t=0, and we can use

up to k=4 junctions, then the quickest way is this path: 1 → 2 → 0 with total estimated traveling time of: 3+1 = 4

minutes.

The shortest path from s=1 to t=0 with no more than k=4 junctions in this sample Singapore map

Query(3, 2, 4): If Ket Fah’s current position is at vertex s=3, the chosen hospital is at vertex t=2, and we can use

up to k=4 junctions, then there is no path possible, so we output ‐1 as our answer.

There is not path from s=3 to t=2 with no more than k=4 junctions in this sample Singapore map

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2916 3/4

Subtask A Constraints (40 points)

Time Limit: 2s.

On a rather ‘impossible case’ that simplifies this problem, the road network in Singapore is an undirected weighted

tree, 1 ≤ V ≤ 1 000 (you can infer E from V), 1 ≤ Q ≤ 100 000, 0 ≤ s, t < V, and k=V. We guarantee that weight(u, v)

= weight(v, u) for all vertices u and v in the graph.

A simplified Singapore Map (Tree); For your convenience, view this undirected weighted tree at VisuAlgo; This is the

visualization of the first test case in the Sample Input

Query(0, 3, 4): If Ket Fah’s current position is at vertex s=0, the chosen hospital is at vertex t=3, and we can use

up to k=4 junctions, then the quickest way is this path: 0 → 1 → 2 → 3 with total estimated traveling time of: 1+5+2 =

8 minutes.

The shortest path from s=0 to t=3 with no more than k=4 junctions in this simplified Singapore map (Tree)

Query(0, 2, 4): If Ket Fah’s current position is at vertex s=0 and the chosen hospital is at vertex t=2, and we can

use up to k=4 junctions, then the quickest way is this path: 0 → 1 → 2 with total estimated traveling time of: 1+5 = 6

minutes. The visualization of this path is similar as above.

Hint: Have you seen a PS with insane number of queries like this before?

Sample Input

2

4

1 1 1

2 0 1 2 5

2 1 5 3 2

1 2 2

4

0 3 4

0 2 4

0 1 4

0 0 4

2

1 1 7

1 0 7

4

0 0 2

0 1 2

1 0 2

1 1 2

Sample Output

8

6

1

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2916 4/4

© Copyright 20092017 National University of Singapore. All Rights

Reserved.

Terms of Use | Privacy | Nondiscrimination

MySoC | Computing Facilities | Search | Campus Map

School of Computing, National University of Singapore

0

0

7

7

0

Generating Test Data

The given sample input/output are for illustration purpose and are not enough to verify the correctness of your

solution.

You are encouraged to generate and post additional test data in CS2010 Facebook group.

Please use BleedingVerifierA.java (click to view) to verify whether your custommade test data conform with the

required specifications.

Problem Author

Dr Steven Halim/Dr Chong Ket Fah

For CS2010.

Footnotes

1To simplify this problem, let’s assume that this time estimation is accurate and there is no traffic jam in Singapore.

2The reason of this constraint k is because when bleeding starts, you don’t want to move the affected joint as much

as possible. However with many junctions there will be much starting and stopping of the car and this will affect the

injured joint. Thus Ket Fah want the taxi drive or his brother to cross no more than k junctions (vertices in Singapore

map) along the shortest path from vertex s to vertex t.

3Yes, Singapore map does not looks like this, but let’s just assume it is.

4

If needed, you can write additional helper methods/functions to simplify your code.

Submission (Course)

Select course: CS2010 (2016/2017 Sem 2) Data Structures and Algorithms II

Your Files:

SUBMIT (only .java, .c, .cpp and .h extensions allowed)

To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be

added to the upload queue. You can repeat this step to add more files. Check that you have all the files

needed for your submission. Then click on the Submit button to upload your submission.

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2917 1/3

Logged in as: e0009011

CodeCrunch

Home My Courses Browse Tutorials Browse Tasks Search My Submissions Logout

CS2010 2016/2017 Sem2: PS5 B

Tags & Categories

Tags:

Categories:

Related Tutorials

Task Content

A bleeding episode, v2017 (Subtask B)

The Actual Problem Description

Please refer to Subtask A for the full problem description.

Subtask B Constraints (additional 30 points)

Time Limit: 1s.

The road network in Singapore is a directed weighted graph, 1 ≤ V ≤ 1 000, 0 ≤ E ≤ 200 000, 1 ≤ Q ≤ 10 000, 0 ≤ s ≤

9, 0 ≤ t < V, and k=V.

In fact, the first examples shown earlier in Subtask A and replicated below fits this description (see the first graph and

the first set of queries in Sample Input/Output).

A sample Singapore map; Create and view this directed weighted graph at VisuAlgo

Query(0, 3, 4): If Ket Fah’s current position is at vertex s=0, the chosen hospital is at vertex t=3, and we can use

up to k=4 junctions, then the quickest way is this path: 0 → 1 → 2 → 3 with total estimated traveling time of: 2+3+7 =

12 minutes.

Search search for… in NUS Websites

NUS WebMail IVLE LIBRARY MAPS

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2917 2/3

The shortest path from s=0 to t=3 with no more than k=4 junctions in this sample Singapore map

Query(1, 0, 4): If Ket Fah’s current position is at vertex s=1, the chosen hospital is at vertex t=0, and we can use

up to k=4 junctions, then the quickest way is this path: 1 → 2 → 0 with total estimated traveling time of: 3+1 = 4

minutes.

The shortest path from s=1 to t=0 with no more than k=4 junctions in this sample Singapore map

Query(3, 2, 4): If Ket Fah’s current position is at vertex s=3, the chosen hospital is at vertex t=2, and we can use

up to k=4 junctions, then there is no path possible, so we output ‐1 as our answer.

There is not path from s=3 to t=2 with no more than k=4 junctions in this sample Singapore map

Hint: Have you seen a PS with insane number of queries like this before?

Sample Input

2

4

3 1 2 2 9 3 15

1 2 3

2 0 1 3 7

0

3

0 3 4

1 0 4

3 2 4

4

1 1 1

2 0 1 2 5

2 1 5 3 2

1 2 2

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2917 3/3

© Copyright 20092017 National University of Singapore. All Rights

Reserved.

Terms of Use | Privacy | Nondiscrimination

MySoC | Computing Facilities | Search | Campus Map

School of Computing, National University of Singapore

4

0 3 4

0 2 4

0 1 4

0 0 4

Sample Output

12

4

‐1

8

6

1

0

Generating Test Data

The given sample input/output are for illustration purpose and are not enough to verify the correctness of your

solution.

You are encouraged to generate and post additional test data in CS2010 Facebook group.

Please use BleedingVerifierB.java (click to view) to verify whether your custommade test data conform with the

required specifications.

Problem Author

Dr Steven Halim/Dr Chong Ket Fah

For CS2010.

Submission (Course)

Select course: CS2010 (2016/2017 Sem 2) Data Structures and Algorithms II

Your Files:

SUBMIT (only .java, .c, .cpp and .h extensions allowed)

To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be

added to the upload queue. You can repeat this step to add more files. Check that you have all the files

needed for your submission. Then click on the Submit button to upload your submission.

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2918 1/3

Logged in as: e0009011

CodeCrunch

Home My Courses Browse Tutorials Browse Tasks Search My Submissions Logout

CS2010 2016/2017 Sem2: PS5 C

Tags & Categories

Tags:

Categories:

Related Tutorials

Task Content

A bleeding episode, v2017 (Subtask C)

The Actual Problem Description

Please refer to Subtask A for the full problem description.

Subtask C Constraints (additional 30 points)

Time Limit: 1s.

The road network in Singapore is a directed weighted graph, 2 ≤ V ≤ 1 000, 0 ≤ E ≤ 200 000, 1 ≤ Q ≤ 20, 0 ≤ s, t < V,

1 ≤ k ≤ min(V, 20) , and s != t.

Let’s take a relook at the sample graph that has been shown in Subtask A earlier:

A sample Singapore map; Create and view this directed weighted graph at VisuAlgo

Now recall that the answer for Query(0, 3, 4) is: 0 → 1 → 2 → 3 with total estimated traveling time of: 2+3+7 = 12

minutes. Notice that this path uses 4 junctions (vertices).

Search search for… in NUS Websites

NUS WebMail IVLE LIBRARY MAPS

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2918 2/3

The shortest path from s=0 to t=3 with no more than k=4 junctions in this sample Singapore map

Now if we have Query(0, 3, 3), then path: 0 → 1 → 2 → 3 shown above is invalid as it uses 4 junctions. The valid

shortest path from s=0 to t=3 that uses no more than k=3 junctions is path: 0 → 3 with total estimated traveling time

of: 15 minutes. This path is 3 minutes longer than the true shortest path without Ket Fah’s restriction of not crossing

more than k junctions but it is now the best answer

1

for this Subtask C.

The new valid shortest path from s=0 to t=3 with no more than k=3 junctions in this sample Singapore map

Sample Input

1

4

3 1 2 2 9 3 15

1 2 3

2 0 1 3 7

0

12

0 3 4

0 3 3

0 3 2

0 3 1

1 0 4

1 0 3

1 0 2

1 0 1

3 2 4

3 2 3

3 2 2

3 2 1

Sample Output

12

15

15

‐1

4

4

‐1

‐1

‐1

‐1

‐1

‐1

Generating Test Data

The given sample input/output are for illustration purpose and are not enough to verify the correctness of your

solution.

You are encouraged to generate and post additional test data in CS2010 Facebook group.

Please use BleedingVerifierC.java (click to view) to verify whether your custommade test data conform with the

required specifications.

Problem Author

3/22/2017 CodeCrunch

https://codecrunch.comp.nus.edu.sg/task_view.php?tid=2918 3/3

© Copyright 20092017 National University of Singapore. All Rights

Reserved.

Terms of Use | Privacy | Nondiscrimination

MySoC | Computing Facilities | Search | Campus Map

School of Computing, National University of Singapore

Dr Steven Halim/Dr Chong Ket Fah

For CS2010.

Footnotes

1There is one other possible path from s=0 to t=3 that uses no more than k=3 junctions, path: 0 → 2 → 3, but it has

longer estimated traveling time of: 9+7 = 16 minutes.

Submission (Course)

Select course: CS2010 (2016/2017 Sem 2) Data Structures and Algorithms II

Your Files:

SUBMIT (only .java, .c, .cpp and .h extensions allowed)

To submit multiple files, click on the Browse button, then select one or more files. The selected file(s) will be

added to the upload queue. You can repeat this step to add more files. Check that you have all the files

needed for your submission. Then click on the Submit button to upload your submission.

WhatsApp us