Move your Money

Figure: see image.

Your goal is to move your money, minimizing losses to taxes (edges) and bribes (nodes).

In choosing a path, choose the lowest cost (shortest path) primarily based on edge-weight, and only secondarily breaking ties by bribe rate if there are two equivalent shortest paths.

You are required to edit 4 files and their dependencies:

• MyGraph.h (make sure you spell this and all functions correctly); fully implement all functions in this file. It is easier to just define your functions in the h file.
• import_problem.cpp
• import_graph.cpp
• dijkstra.cpp
• You can submit other hpp or h files, though you are not required to do so.
• Note: don't rely on cpp files other than those listed being compiled (they will not be).
• Make sure to include any header files you use (e.g., heap.h) in the repository!

Input and output files

• Input will be via cin / standard input (as before).
• Output will be via cout / standard output (as before).

Input files

• We give you three examples of weighted directed graphs.
• The file format is csv (comma separated value) file containing a matrix of exchange rates, with row and column headers as node-names and bribe costs (in parentheses).
• Try opening this file in LibreOffice or MS-Excel; csv is the original spreadsheet. The first thing for you to do is read up on the csv format, and make sure you understand it!
• The matrix file also has a question at the end. You must parse this to determine the desired path to be printed.
• Note: the number of commas is significant. Make sure you understand the file format.
• Left row indices are "from" and top column headers are to in the graph.

Output files

• Example given.
• You will need to add/remove plurality with currency names, including new ones that we test with.
• We will not test with all real-world currency names (they will all be single-word names with no spaces)
• Make sure formatting matches; use methods below:
• Make sure to round numbers the same as we do in the example outputs: truncate decimals longer than 1, and eliminate trailing 0s, so 2.0 becomes 2, and 2.222 becomes 2.2 in output.

Running

$ g++ anymain.cpp (e.g., pa09.cpp) dijkstra.cpp import_problem.cpp import_graph.cpp -std=c++11
$ ./a.out your_output.txt
$ diff your_output.txt sample_output.txt

Note: We will not be running with g++ *.cpp, so don't use another cpp file. Name your files and functions correctly!