Description

Tim and Ray are two students from the Department of Computer Science at NTHU. Before graduation, they plan to embark on a walking trip around Taiwan. However, as college students facing a future where AI may reduce job opportunities, they have extremely limited funds. Therefore, they must carefully plan the expenses of their entire journey.

First, they need to determine their destination. Ray lives in Tamsui and survives by eating Tamsui Agei (a traditional Taiwanese food) every day. Before graduation, he hopes to taste food other than Agei and rice noodles. Tim has “riding gongwan” (Hsinchu’s famous pork balls, humorously described as a mode of transportation). for four years throughout his university life and now wishes to learn how to use other modes of transportation.

While they were troubled by their decision,
Allen made a suggestion: “Why not go to Pingtung? Not only can you eat delicious tuna, but you can also ride at Eluanbi Lighthouse. Most importantly, you may even see the long-lost Sam.”
Ray: “Oh right! I haven’t seen Sam in a long time.”
Tim: “He still owes me a McDonald’s.”
Allen: “Does Pingtung even have McDonald’s?”
Ray: “I think they only have Dandan Burger.”
Tim: “Fine, Dandan is fine! As long as he treats us, I’m satisfied.”
Ray: “Alright then, it’s Pingtung!!!”

After some time planning, they decided to travel throughout the entire summer vacation.
Allen: “The entire summer!? Doesn’t that mean we could eventually reach anywhere even if we wander randomly?”
Tim: “Exactly. To avoid worrying about time, I already quit my summer camp job.”
Thus, the only thing they truly need to care about is money.
Ray: “Great! Now I can fully enjoy the journey of finding Sam. Tuna, here I come!”
Allen: “I just received a phone call from Sam’s father. Since he is a skilled mountaineer, he can lend us a tent!”
Ray: “Then we only need to manage our food supply!”
Tim: “I have implemented software that lists the unit price of food in different cities.”
Allen: “And I built an app that calculates how many units of food are consumed when traveling between certain cities.”
Ray: “That’s perfect! In that case, I will find a way to obtain a program that combines your information and computes how much money we need to prepare.”

Additionally, Prof. C provides K vouchers, each of which can be exchanged for one unit of food for free.

Since Ray is a good friend of Prof. C, and you are Prof. C’s students, naturally this task is handed over to you.

 

According to Ray’s notes, you are given a map containing N cities and M undirected roads.

• The unit price of food in city_j is V_j .
• The maximum amount of food they can carry is C units.
•  At the beginning of the journey, they start at the starting city with 0 units of food.

At any city:

•  They may purchase any non-negative integer amount of food.
•  They may perform multiple purchase operations.
• The total amount of food after purchasing must not exceed C.
• Staying or purchasing food in a city does not consume food.

For each undirected road_i, connecting cities u_i and v_i, traveling through the road consumes a fixed amount of food cost_i:

• They may traverse the road only if the current food amount f ≥ cost_i.
•  After traversing, the remaining food becomes f − cost_i.
• Discarding food is prohibited.

Refill system:

• At certain cities, Ray’s friends will help refill their food automatically.
• Upon arriving at (or starting the journey at) city_i, if their current food amount f is less than T_i, their food amount becomes min(f + s_i, C).
• This refill does not consume any money, time, or vouchers.
• The food amount after refilling must still not exceed the capacity C.
• If their food amount is already greater than or equal to T_i,no refill occurs.

The order of actions is refill -> buying or voucher transactions (order doesn't matter)
Once they first arrive at the destination city, the journey is considered completed. The remaining food amount does not matter, and no refund is provided.
Your task is to compute the minimum total amount of money required to complete the journey.

Problem Constraints: Header Usage
Standard Phrasing:

You may use any headers from the C++ Standard Library.

Sample Explanation

The optimal route is hsinchu → miaoli → hsinchu → taichung → changhua → pingtung.

At hsinchu, Ray's friend automatically refills 3 units of food for free. Tim then uses the voucher to gain 1 more unit, bringing the total to 4 units.

They then travel to miaoli (consuming 3 units, food: 4→1) and purchase 4 units of food at the local price of 50, spending 200 in total.

They backtrack to hsinchu (consuming 3 units, food: 5→2), where the refill triggers again (since 2<5), restoring 3 free units (food: 2→5).

From hsinchu, they travel directly to taichung via the shortcut (consuming 3 units, food: 5→2), then continue to changhua (consuming 2 units, food: 2→0).

Upon arriving at changhua, the refill triggers (since 0<2), providing 8 free units (food: 0→8).

Finally, they travel to pingtung (consuming 8 units, food: 8→0), completing the journey.

The total cost is 50×4=200.

by gemini

testcases

1-2	N ≤ 10, K=0, R=0
3-4	K=0, R=0
5-6	K=0
7-8	R=0
9-10	No Limit

 

Input

The first line contains five integers N M C K R.

• N: the number of cities
• M: the number of undirected roads
• C: the maximum food capacity
• K: the number of vouchers
• R: the number of cities that provide refill

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10⁵
• 1 ≤ C ≤ 100
• 0 ≤ K ≤ 10
• 0 ≤ R ≤ 10

The next N lines each contain:

CityName_j V_j

•  1 ≤ j  ≤ N
• CityName_j is the name of a city.
• Each city name consists only of lowercase English letters.
• The length of each name does not exceed 30 characters.
• All city names are distinct.
• The value V_j denotes the unit price of food in that specific city.1 ≤ V_j ≤ 10⁵.

The next M lines each contain three space-separated items:

City_u City_v cost_i

• This represents an undirected road.
• 1 ≤ cost_i ≤ 100.
•  City_u and City_v  must be different.
• Both cities are guaranteed to appear in the city list.

After the road descriptions, the next R lines each contain:

CityName_i T_i s_i

• CityName_i​ is a city that provides refill
• T_i​ is the threshold, 0 ≤ T_i ≤ 10⁵
• s_i the refill amount, 0 ≤ si ≤  10⁵
• It is guaranteed that all refill cities are distinct.

Upon arriving at CityName_i​​:

• If the current food amount is less than T_i​, it will increase by s_i units
• The food amount after refilling must not exceed C

The last line contains two strings:

StartCity EndCity

• The starting city and destination city are guaranteed to appear in the city list.
•  StartCity and EndCity must be different.

Note: The graph is not guaranteed to be connected.

Output

• If it is possible to reach the destination, output a non-negative integer representing the minimum total cost.
• If it is impossible to reach the destination, output the string Impossible (spelling must match exactly).

 

Sample Input  Download

Sample Output  Download

Discuss