Description

Following an unforeseen enhancement to Wakunda's anti-spy system, professional spy Anya was confronted with a challenge. The anti-spy countermeasures made by Wakunda had made her usual digital spy communication methods nearly infeasible, forcing her to hand-deliver an essential message from Wakunda to her headquarters with the help of her reliable partner, You!

Anya has good memory since she can remember the distance between two places. However, she is not good at math and needs your help to make a program to calculate the shortest-path distance between your current location to a certain location and calculate the distance. Having the shortest-path distance calculation is crucial for this mission to allow both you and Anya to schedule your journey and allocate the necessary supplies. Furthermore, there's no need for concern about remembering the sequence of locations to reach your destination since Anya can assist you spontaneously throughout the journey, both of you only cares about the shortest-path distance to reach your destination from all possible path.

Anya suggests employing Dijkstra’s algorithm to create the shortest-path distance calculator for this mission, which subsequently inspires the operation's name.

Your code should only contain the following library & namespace, you might receive a score deduction if you’re using the other libraries:

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string.h>
#include<cmath>
using namespace std;

Graph Element

• Node/Vertex: Represent the location

• Edge: Represent the distance between 2 locations

Input

1) Location Insertion

INSERT_LOCATIONS <total_nodes>

<total_nodes> represent the maximum number of location in the test case. For example, if we put this input line:

INSERT_LOCATIONS 100

Then you will have 100 locations of vertex/node starting from ID 1 until 100. Where vertex/node with an ID of 1 is always your location (source)

It’s guaranteed that:

• 2 <= total_nodes <= 100

• 1st vertex/node is always your initial location

 

2) Distance Insertion

INSERT_DISTANCE <location1> <location2> <distance>

For example, we want to connect two locations with ID number 9 and 6, which has a distance of 200:

INSERT_DISTANCE 9 6 200

The previous input line is also equivalent with:

INSERT_DISTANCE 6 9 200

It's guaranteed that:

• Edges consisting of the same pair will not be inserted more than once

• 1 <= location1 <= total number of nodes

• 1 <= location2 <= total number of nodes

• location1 != location2

• <distance> is integer

• 1 <= <distance> <= 10⁵

 

3) Shortest Path Distance Calculation

CALCULATE <destination_id>

The function will generate an output representing the shortest-path distance from your location (ID=1) to your destination. The <destination_id> parameter is the ID of your destinated location.

For example, we use the following input to calculate the distance between your current location (ID=1) to a location with ID = 6

CALCULATE 6

It's guaranteed that:

• 1 < <destination_id> <= <total_nodes>

• This function can be called multiple times in the test case

• This function might be called before we finished all the location/distance insertions

• The shortest path between your location and to destination when this function is called in every test case never consists of an infinite distance (you don’t need to worry if the output distance is infinite).

 

4) Terminate Application

TERMINATE

When the user inputs the terminate command, your application will be ended.

Output

Output must be created immediately when the following "3) Shortest Path Distance Calculation" input was triggered

CALCULATE <destination_id>

The function will generate an output representing the shortest-path distance from your location (ID=1) to your destination. The <destination_id> parameter is the ID of your destinated location.

<the distance of the shortest path> // without newspace in the end of the line
<new line>

For example, we use the following input to calculate the distance between your current location (ID=1) to a location with ID = 6

CALCULATE 6

If the shortest path distance between your location to the node with ID 6 is 900, then the output will be:

900

It's guaranteed that:

• This function can be called multiple times in the test case

• This function might be called before we finished all the location/distance insertions

• The shortest path between your location and to destination when this function is called in every test case never consists of an infinite distance (you don’t need to worry if the output distance is infinite).

 

Sample Input  Download

Sample Output  Download

Tags

Discuss