Description
In this quiz, you will need to implement three operations, Add, Delete, Shortest to maintain a directed graph with positive and negative edges. The vertex representation is an integer. For example, vertex 0, vertex 1, and so on.
Below are the descriptions of these three operations.
Operations:
- Add A B c: It means there is an edge from A to B with weight equals to integer c. If there already exists an edge, update to the new one. (Delete the original edge and add the new edge)
- Delete A B: It means there is no more an edge from A to B.
- Shortest A B: It means you need to calculate the shortest path from A to B and also print the nodes on this path in traversing order. However, if there exists any negative cycle on this path or it doesn’t exist any shortest path from A to B, print “error”.
For example:
(i) Shortest 1 4: 6 1,2,4
(ii) Shortest 0 4: error
(iii) Shortest 0 3: error
(iiii) Shortest 1 0: error
Notice: You are allowed to use stl in this problem except for those directed functions which calculate shortest path and negative cycle.
Input
In each testcase, the first input N will be the number of vertices in this graph. N will less than 1000 and the vertex key will be 0 to N-1. Several operations will follow after first input.
Output
For command “Shortest”, you will need to print the output.