[SOLVED] Csc3100 programming assignment 4 1 mirror 1.1 description figure 1: an example map of the city lee wants to show his new invention, a special mirror

1.1 Description
Figure 1: An example map of the city
Lee wants to show his new invention, a special mirror, to his friends. These friends are scattered over
the city, which consists of n nodes connected by m undirected edges. It takes wi time to pass through
an edge, i = 1, …, m. Figure 1 shows a map of a city. For a path from the starting node s to the
ending node t, Lee decided that he must go through k specific undirected edges E = {e1, e2, . . . , ek}.

Please note that:
1. There is no pass order requirement for these specific edges;
2. If e1 = (u, v), Lee could pass the edge from u to v, he also could pass the edge from v to u.
Lee could start from different nodes and end at different nodes. In addition, a pair consisting of a
starting node sj and an ending node tj corresponds to a set of edges Ej , j = 1, …, q, which Lee must
pass through. Since time is of the essence in the city, Lee needs to find the shortest possible path
through all the specified edges.

Here is a detailed example around Figure 1 with q = 2:
1. Lee starts from node s1 = 1 and ends at node t1 = 5. Besides, he is required to pass through an
undirected edge E1 = {(1, 6)}(i.e. edge between 1 and 6). Then, his path is 1 → 6 → 1 → 3 →
7 → 5;
2. When Lee starts from node s2 = 2 and ends at node t2 = 7, he has to pass through two undirected
edges E2 = {(1, 3),(1, 2)}. Therefore his path is 2 → 1 → 3 → 7.

1.2 Input
• The first line contains three integers n, m, and q, indicating the number of nodes n, the number
of edges m, and the number of planned paths q.

• The next m lines each contain three integers u, v, and w. These represent an edge between nodes
u and v, with a traversal time of w. The edge described in the i-th line is numbered i.
• For each of the next q blocks, the first line contains an integer ki
.

The following line contains ki
integers e1, e2, . . . , eki
, indicating the indices of the edges Lee must pass through.
• The next q lines each contain two integers si and ti
, indicating the starting point si and the
ending point ti of each path.

1.3 Output
• q lines, i-th line indicating the smallest amount of time of i-th paths.
Sample Input 1
7 9 2
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
3 7 1
5 7 2
1
4
2
1 3
1 5
2 7
Sample Output 1
22

The graph of Sample 1 is shown in Figure 1.
Sample Input 2
See attached q1sample2 . in
Sample Output 2
See attached q1sample2 . out
Sample Input 3
See attached q1sample3 . in
Sample Output 3
See attached q1sample3 . out

Problem Scale & Subtasks
• k ≤ 5, q ≤ 100, wi ≤ 2 × 103
,
5
• n ≤ 1000, n − 1 ≤ m ≤ 2 × 103
, and 1 ≤ s, t ≤ n
Test Case No. Constraints
1-2 m, n ≤ 100
3-5 n ≤ 500
6-10 n ≤ 1000

2.1 Description
(a) The graph of 0-th day (b) The graph of 1-th day (c) The graph of 2-th day
Figure 2: An example map of the park.

Heath wants to have a date with his beloved Kathy. He decides to invite Kathy for a walk in a huge
park. This park can be described as an undirected dynamic graph, consisting of n flowerbeds
and m undirected edges connecting these flowerbeds. Each edge is filled with violets, Kathy’s favorite
flower. The i-th edge has wi violets, i = 1, …, m.

There are q + 1 days Heath could choose to have the date. Besides, at the beginning of i-th day,
i = 0, 1, 2, …, q, the number of violets on a set of edges will change, where ki edges will be affected.
Please note that i = 0 indicating the park has not changed yet.

Heath wants to plan a no-duplicate-node path where he and Kathy will start from point si and end
their tour at point ti
. He hopes to maximize the minimum number of violets encountered on any noduplicate-node path throughout the entire path. You are expected to give him the maximum number
of these values each day.

A detailed example around Figure 2 with q = 2 is provided in the following. Heath will choose one of
the 3 days to date:
• At the beginning of 0-st day, the graph is shown in Figure 2(a);
• At the beginning of 1-st day, k1 = 1. The value on edge (2, 3) changes to 4;
• At the beginning of 2-nd day, k2 = 2. The value on edge (3, 4) changes to 1 and the value on
edge (1, 3) changes to 5;

Take Figure 2(a) as an example, Heath wants to start from 1 and end at 4 on 0-th day. There are
three no-duplicate-node paths he can choose to date:
1. 1 → 2 → 3 → 4, with the number of violets on the path being 2, 1, and 4 respectively, and the
smallest number is 1;
2. 1 → 3 → 4, with the number of violets on the path being 3, 4 respectively, and the smallest
number is 3;

3. 1 → 4, with the number of violets on the path being 6, and the smallest number is 6.
Therefore, we choose the path with the largest minimum number, which is 1 → 4, and the answer is 6.

2.2 Input
• The first line contains two integers n and m, indicating there are n flowerbeds and m paths;
• The next m lines each contain three integers u, v, and w, representing a path between flowerbeds
u and v, lined with w violets;

• The next line contains an integer q, the number of changes that will occur;
• For each of the next q blocks, the first line contains an integer ki
, the number of paths affected
by the change. The following ki
lines for each contain three integers a, b, and c, indicating that
the path between flowerbeds a and b now has c violets;

• For next q + 1 lines, there including two integer si
, ti
indicating that Heath will start from
flowerbed si and end at flowerbed ti
.

2.3 Output
• q + 1 integer, indicating the maximum number of fewest violets after every change.
Sample Input 1
4 5
1 2 2
2 3 1
1 3 3
3 4 4
1 4 6
2
1
2 3 4
2
1 3 5
3 4 1
1 4
2 4
1 2
Sample Output 1
6
4
4
The dynamic graph of Sample 1 is shown in Figure 2.
Sample Input 2
See attached q2sample2 . in
Sample Output 2
See attached q2sample2 . out
Sample Input 3
See attached q2sample3 . in
Sample Output 3
See attached q2sample3 . out

Problem Scale & Subtasks
• 1 ≤ si
, ti ≤ n,
• m ≤ 2 × 104
, q ≤ 100, wi ≤ 104
, and
• Heath can always reach t starting from s.
Test Case No. Constraints
1-2 m, n ≤ 100 and ki = 1
3-5 n ≤ 100 and ki ≤ 10
6-10 n ≤ 104 and ki ≤ 10

3.1 Description
Figure 3: An example map of La Mancha Land
Don plays the role of a hero in the La Mancha Land parade, defeating monsters and obtaining treasures.
Don has two attributes: health points (HPs) and spirit points (SPs). Since Don is very powerful, she
can decide these values herself. Her adventure map can be viewed as an undirected simple connected
graph with n nodes and m edges. Don needs to start from her hometown s and reach the treasure
location t.

Each time she passes an edge, her spirit point decreases by 1. Additionally, each edge has a monster
with an attack power of ai
. If Don’s spirit point is t, she loses 
ai
t

health points. The monsters cannot
be defeated. Therefore, if Don passes through the same edge twice, she will suffer damage twice.

To entertain the parade-goers, she wants to reach the destination at the most desperate moment, which
means her spirit and health points are both exactly 0. While preparing her costume for the
performance, she asks you to determine the minimum initial health points she needs to achieve
her goal.

Taking Figure 3 as an example, if Don starts from node 1 and ends at node 3, she has two paths to
choose from:
• 1 → 2 → 3: at node 1, Don has SP = 2 and HP = 4; and at node 2, Don has SP = 1 and HP =
3; and at node 3, his SP = 0 and HP = 0, which satisfies the requirement.
• 1 → 3: at node 1, SP = 1, HP = 5; at node 3, SP = 0, HP = 0.
Therefore, the minimum number of health points Don needs to maintain at the starting node is 4.

3.2 Input
• The first line contains four integers n, m, s, and t, indicating the number of nodes n, the number
of edges m, Don starts from node s and ends at node t;
• The next m lines each contain three integers u, v, and ai
, representing an edge between node u
and v, the attack power of monster is ai
.

3.3 Output
• One integer, indicating the least health point Don needs.
Sample Input 1
3 3 1 3
1 2 2
1 3 5
3 2 3
Sample Output 1
4

The graph of Sample 1 is shown in Figure 3.
Sample Input 2
See attached q3sample2 . in
Sample Output 2
See attached q3sample2 . out
Sample Input 3
See attached q3sample3 . in
Sample Output 3
See attached q3sample3 . out

Problem Scale & Subtasks
Test Case No. Constraints
1-2 m, n, αi ≤ 10
3-6 n ≤ 103
, m ≤ 2 × 103 and αi ≤ 10
7-8 n ≤ 2 × 104
, m ≤ 4 × 104
, and αi = 1
9-10 n ≤ 2 × 104
, m ≤ 4 × 104
, and αi ≤ 100