C Language Title: Quests from the Queen
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
Related questions
Question
C Language
Title: Quests from the Queen

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.

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

This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps

Knowledge Booster
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
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education

Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON

Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON

C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON

Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning

Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education