Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
C Language Title: Quests from the Queen

C Language Title: Quests from the Queen

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

C Language

Title: Quests from the Queen

Output Output contains an integer in a line representing the minimum time Athin needed to finish all the quests and return back to city 1. Sample Input #1 5 7 3 8 |1 2 3 2 3 6 3 4 2 45 3 5 1 2 5 25 5 3 4 2 3 4 Sample Output #1 11 Explanation for the sample input/output #1 Athin can visit cities 5, 4 and 3 in order; completing two of the quests in 7 units of time. He then waits for 1 unit of time. His mana is now at 100% and he teleports to city 2 instantly. He then returns to city 1 to submit the tea leaves. The total time taken is 11 units of time. Sample Input #2 5 71 8 1 2 3 2 3 6 3 4 2 4 5 3 5 1 2 5 25 5 3 4 2 Sample Output #2 6 Explanation for the sample input/output #2 Athin can just go to city 2 and then back to city 1 without using his self-teleportation spell. It takes him 6 units of time in total.
Transcribed Image Text:Output Output contains an integer in a line representing the minimum time Athin needed to finish all the quests and return back to city 1. Sample Input #1 5 7 3 8 |1 2 3 2 3 6 3 4 2 45 3 5 1 2 5 25 5 3 4 2 3 4 Sample Output #1 11 Explanation for the sample input/output #1 Athin can visit cities 5, 4 and 3 in order; completing two of the quests in 7 units of time. He then waits for 1 unit of time. His mana is now at 100% and he teleports to city 2 instantly. He then returns to city 1 to submit the tea leaves. The total time taken is 11 units of time. Sample Input #2 5 71 8 1 2 3 2 3 6 3 4 2 4 5 3 5 1 2 5 25 5 3 4 2 Sample Output #2 6 Explanation for the sample input/output #2 Athin can just go to city 2 and then back to city 1 without using his self-teleportation spell. It takes him 6 units of time in total.
Quests from the Queen Once upon a time, when magicians were as common as programmers, Athin, a young magic swordsman thought to himself, "Holy heavens, I'm broke." Soon afterwards, he chanted a teleportation spell and ended up on top of the royal palace, the highest point in the empire, which is at city 1. He had an unobstructed vision and identified N cities and M bi-directional roads. The ith road connected cities A, and B, and would expend T; units of time for Athin to travel through. A pair of cities could have multiple roads connecting them, and it was not guaranteed that a trip from any city to any other city would be possible using roads alone. Three seconds later, the queen saw Athin from her tea party and offered K quests. To clear the ith quest, Athin had to go to city Q, to collect tea leaves. Since all of quests were just collecting tea leaves, the queen didn't mind if Athin completed his quests in any order. After completing all the quests, he had to return back to the queen in this royal palace. Athin had learned three magic spells. One of them was the ultra-swift-space-time-slash, which lets him slash the tea leaves in no time at all and instantly teleports whatever tea leaves he had slashed into his trusty pocket. As such, while it may take him some time to travel between cities, the tea leaves collection process itself was instantaneous. The second magic spell was the self-teleportation spell which required him to chant words. This ridiculous spell, unlike the ultra-swift-space-time-slash which used practically zero Mana, will consume 100% of his Mana upon usage. However, just like the first magic spell, the process of chanting and teleporting also happened instantaneously. Regardless of his activity, Athin could recover his Mana passively and it took him S units of time to restore 100% of his Mana. Obviously, his Mana capacity was not unlimited and would not go over 100%. Regrettably, he had just used his ridiculous teleportation spell and listening to the queen did not contribute towards restoring his Mana either, resulting in 0% Mana. Wasting no time at all, he instantly activated his third magic spell which lets him peer to the future, intrude an unfortunate soul's lucid dream, and forced them to write a program to calculate the least amount of time required for Athin to complete his quests. You're the unfortunate soul. Input Input begins with a line containing four integers N M K S (2 <N < 100 000; 1 < M < 200 000; 1 < K s min(16, N – 1); 1 < S < 10°) representing the number of cities, number of roads, number of quests, and the time needed to refill his Mana from 0% to 100%, respectively. The next M lines each contains three integers A, B, T, (1 < Aj, B, < N; A, # B;; 1 < T; < 10º) representing the ith bi-directional road connecting cities A, and B, and it takes T; unit of time to pass it. The last line contains K integers Q, in increasing order (2 < Qi < N) representing the location of the ith quest.
Transcribed Image Text:Quests from the Queen Once upon a time, when magicians were as common as programmers, Athin, a young magic swordsman thought to himself, "Holy heavens, I'm broke." Soon afterwards, he chanted a teleportation spell and ended up on top of the royal palace, the highest point in the empire, which is at city 1. He had an unobstructed vision and identified N cities and M bi-directional roads. The ith road connected cities A, and B, and would expend T; units of time for Athin to travel through. A pair of cities could have multiple roads connecting them, and it was not guaranteed that a trip from any city to any other city would be possible using roads alone. Three seconds later, the queen saw Athin from her tea party and offered K quests. To clear the ith quest, Athin had to go to city Q, to collect tea leaves. Since all of quests were just collecting tea leaves, the queen didn't mind if Athin completed his quests in any order. After completing all the quests, he had to return back to the queen in this royal palace. Athin had learned three magic spells. One of them was the ultra-swift-space-time-slash, which lets him slash the tea leaves in no time at all and instantly teleports whatever tea leaves he had slashed into his trusty pocket. As such, while it may take him some time to travel between cities, the tea leaves collection process itself was instantaneous. The second magic spell was the self-teleportation spell which required him to chant words. This ridiculous spell, unlike the ultra-swift-space-time-slash which used practically zero Mana, will consume 100% of his Mana upon usage. However, just like the first magic spell, the process of chanting and teleporting also happened instantaneously. Regardless of his activity, Athin could recover his Mana passively and it took him S units of time to restore 100% of his Mana. Obviously, his Mana capacity was not unlimited and would not go over 100%. Regrettably, he had just used his ridiculous teleportation spell and listening to the queen did not contribute towards restoring his Mana either, resulting in 0% Mana. Wasting no time at all, he instantly activated his third magic spell which lets him peer to the future, intrude an unfortunate soul's lucid dream, and forced them to write a program to calculate the least amount of time required for Athin to complete his quests. You're the unfortunate soul. Input Input begins with a line containing four integers N M K S (2 <N < 100 000; 1 < M < 200 000; 1 < K s min(16, N – 1); 1 < S < 10°) representing the number of cities, number of roads, number of quests, and the time needed to refill his Mana from 0% to 100%, respectively. The next M lines each contains three integers A, B, T, (1 < Aj, B, < N; A, # B;; 1 < T; < 10º) representing the ith bi-directional road connecting cities A, and B, and it takes T; unit of time to pass it. The last line contains K integers Q, in increasing order (2 < Qi < N) representing the location of the ith quest.
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Structure chart
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS