Description
After wiping himself off everyone’s memories in Spider-Man: No Way Home, Peter Parker, now homeless and cashless, remembers what Aunt May used to tell him “Stop fooling around playing games with your friend Ned and get serious with life!”. Hence, partly inspired by Studio Ghibli’s “Kiki’s Delivery Service” and Uber Eats, he decides to open a food delivery servicing app with the help of other Spider-Mans he secretly recruited from various universes.
As he and the other Spider-Mans will do the task of picking-up and delivering orders, he asked you, a college student, to be the lead developer of a pathfinding algorithm for his app. Provided with the total number of neighborhoods, roads that connect between neighborhoods in the city, and commands. Your task is to create a program that helps the delivery men find the shortest route to their destination, and avoid creating traffic jams at all cost! Welcome to ‘Spider-Man’s Delivery Service: Project Dijkstra’!
Commands:
Order ID src ts
Given three integers ID, src, ts. Create an order with the given request ID. You must then search for the nearest available delivery man by distance to src vertex and assign the driver to go pick-up the order, once assigned that delivery man will not be able to accept other orders until he becomes available again. Furthermore, this order takes up ‘ts’ traffic space on any of the edges (roads) that it goes through, thus you should reserve ‘ts’ traffic space from the available spaces of the edge for all edges this delivery man will use.
If no delivery man is available or traffic is full or you’re unable to reach out to any delivery man due to inadequate traffic space, simply ignore the order (discard order) and output: "Just walk. T-T".
However, if a delivery man is found, please output: “Order {ID} from: {DL}”
*’DL’ represents the driver’s location (the vertex he is found in).
*Note that request ID is not necessarily in ascending or descending order.
Drop ID dst
Your delivery man for the ID order has reached the pick-up location and picked up the food! It’s time to deliver the order from the restaurant (pick-up location) to your client at dst vertex. You must first return the traffic space initially reserved for the delivery man to get to the pick-up location. You must then try to find the shortest path from the pick-up location to the client at dst vertex. Again, you must also reserve the traffic space along the path that the delivery man will take. If a path is found for the order then output the following message: “Order {ID} distance: {TD}”
If no path is available (not enough traffic space), then output: "No Way Home".
The delivery man will then wait at the pick-up location until the program can return and help search for a new path (hopefully the traffic clears up by then). To simplify the problem, if the order’s traffic space is larger than any available space leading to the destination edge, just keep the order waiting infinitely.
*’TD’ represents the total distance traveled by the driver from their starting point to finish (to the client's vertex).
Complete ID
Your delivery man for the ID order has successfully delivered the goods to the client. You must now return the traffic space initially reserved for the delivery man’s route to get to the client’s location. Your delivery man will now become available/idle at the client’s location, ready to accept new orders.
You should then check whether any of the orders initially waiting for the traffic to clear up can now travel to their destination, if so reserve the traffic space accordingly. You must check in order of the ID value, starting from the smallest ID to largest ID value. If no path is available for any of the order you’re checking, output nothing and keep that int ID order waiting. However, if a path is found for a waiting order then output the following message: “Order {ID} distance: {TD}”
*’TD’ represents the total distance traveled by the driver from their starting point to finish (to the client's vertex).
Pathfinding Specifications:
Since there can be multiple shortest pathways in certain cases, to simplify this problem, Peter Parker decides disregard efficiency and issued the following greedy conditions for the algorithm to ensure that your pathfinding program will be as fast and unique as possible:
- When updating the distance cost of adjacent vertices, start updating the vertex from the smallest vertex ID (‘1’).
- When selecting a new vertex to explore for pathways to an objective, the immediate vertex with the shortest travel distance from the source shall be prioritized for exploring new paths. Select the smaller ID vertex if two vertices have the same travel distance.
- If the objective you’re searching for in that specific operation is found through a path and traffic space is adequate, immediately select such path unless a smaller distance path with sufficient space is discovered.
Guarantees & Notes:
- Note that the graph is an undirected connected graph.
- Order ID will be unique (not reused in a new request once declared). And all the source/destination requested in an order is guaranteed to exist in the graph.
- Order ID will not be called if it is already deactivated by Complete(), or an unsuccessful Order().
- Drop(), and Complete() are guaranteed to be called on an ID that has been declared previously in Order(). And Complete() is guaranteed to be called after Drop() on an ID that already has an active path to the client (no Complete() called on an ID where the driver is still waiting for traffic to clear).
- You may focus on Dijkstra implementation and do not need to consider traffic space in test case 1~4.
Input
Input:
In the first line, you will be given three integers: V E D. Where V stands for the number of vertices in the graph (neighborhoods of New York City). E for the total number of edges in the graph (roads between neighborhoods). D for the total number of vertices where at least one driver is present.
Following that D line you will be given a string and two integers: PLACE v c.
String ‘PLACE’ is to signify the placement of a driver at a location. The v represents the ID of the vertex (neighborhood) and the total number of delivery men c positioned in that vertex (initially all delivery men will be available).
Following that, for the next E line, you will be given a string and four integers: EDGE s, d, dis, t.
String ‘EDGE’ is to signify the insertion of an edge to the graph (map). s being the source vertex, and d being the destination vertex of the edge, dis is an integer which stands for the distance between the two vertices through this edge. Lastly, t stands for the traffic capacity, or the available traffic space this edge (road) has.
It will then be followed by a newline to separate the map initialization and the actual queries.
You will then be given an integer C, the total number of commands you will have to perform.
Lastly, for the next C line, you will be given a command that should be performed.
Parameter Size:
1 <= V, dis, t, ts, c <= 100
1 <= E <= V * (V-1)
1 <= D <= V
1 <= C <= 200
1 <= order ID <= 100
*’v’ or vertex ID is in the range of 1-V.
Output
Print the outputs required according to each command. Enter a newline after every output.