```/* SI 335 Spring 2012
* Project 6
*/

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

// Prints an error message and exits ungracefully
void error (const char* msg);

// Looks up the given vertex name in the array of names,
// and returns the index of that vertex in the array.
// Uses the linearSearch algorithm for search in an unsorted array.
int lookup (const string& name, const string* names, int n);

int main(int argc, char** argv) {
// Get the filename
if (argc != 2) {
cerr << "Usage: " << argv[0] << " <graph_file>" << endl;
error("Need graph filename as argument.");
}
ifstream graph(argv[1]);

int n, m;

graph >> n >> m;

if (n <= 0) error("n must be positive");
if (m <= 0) error("m must be positive");

// Declare storage
// Location names are stored in an array of strings
// Edges are stored in a pair of adjacency matrices,
// one for time and one for cost.
// The index of a vertex in either matrix is defined as the
// index of that NAME in the array of strings.
string* names = new string[n];
int** times = new int*[n]; // Note: double pointer = 2-D array
int** costs = new int*[n];
times[0] = new int[n*n];
costs[0] = new int[n*n];
for (int i=1; i<n; ++i) {
times[i] = times[i-1]+n;
costs[i] = costs[i-1]+n;
}

// IMPORTANT: I am using the weight of -1 to stand for "infinity".
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (i == j) {
times[i][j] = 0;
costs[i][j] = 0;
}
else {
times[i][j] = -1;
costs[i][j] = -1;
}
}
}

// Read in the location names
for (int i=0; i<n; ++i)
graph >> names[i];

string uname, vname;
int uind, vind;
int time, cost;
for (int i=0; i<m; ++i) {
graph >> uname >> vname >> time >> cost;
// Look up the index of each name
uind = lookup (uname, names, n);
vind = lookup (vname, names, n);
if (uind < 0 || vind < 0) error ("Invalid edge name");
// Set the weight in each adjacency matrix,
// in BOTH DIRECTIONS (for undirected array)
times[uind][vind] = time;
times[vind][uind] = time;
costs[uind][vind] = cost;
costs[vind][uind] = cost;
}

graph.close();

// Now read in and process the requests
int timeCost;
while (cin >> uname >> vname >> timeCost) {
int uind = lookup (uname, names, n);
int vind = lookup (vname, names, n);
if (uind < 0 || vind < 0) error("Invalid starting/ending point");

/*******************************************************************
* My algorithm for the shortest paths is REALLY BAD.
* What it does is a depth-first EXPLORATION to examine every
* possible path from the starting vertex to find the shortest path
* to the ending vertex. Once the length of the shortest path is
* known, it does a SECOND exploration to find (again) that actual
* path. Notice that this is a depth-first "exploration" as opposed
* to a normal DFS because it is never marking any nodes as "black",
* only gray basically. This makes it have exponential time. SLOW!
******************************************************************/

vector<int> curPath; // The currently-explored path
int curLength = 0;   // The length of curPath
vector<int> fringe;  // vectors make good stacks.
int shortest = -1;   // length of the shortest path found so far

fringe.push_back(uind);
while (!fringe.empty()) {
int cur = fringe.back();
// Search for cur in the curPath (check if that vertex is "gray")
bool white = true;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == cur) white = false;
}
if (white) {
// cur is an unexplored vetex ON THIS PATH.

// Update curLength (stays at 0 if curPath is empty)
if (!curPath.empty()) {
int previous = curPath.back();
curLength += costs[previous][cur] + timeCost*times[previous][cur];
}

// Add cur to the path
curPath.push_back(cur);

if (cur == vind) {
// Found a path to the destination!
if (shortest == -1 || curLength < shortest)
shortest = curLength;

}

// Add all cur's children to the fringe.
// Skip children that are already in curPath though!
for (int child=0; child<n; ++child) {
bool inpath = false;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == child) inpath = true;
}
if (!inpath && costs[cur][child] >= 0)
fringe.push_back(child);
}
}
else {
// cur has just finished being explored, so pop it off.
fringe.pop_back();
curPath.pop_back();
if (!curPath.empty()) {
int previous = curPath.back();
curLength -= costs[previous][cur] + timeCost*times[previous][cur];
}
}
}

if (curLength < 0) error("No path exists");

// Now we know that curLength is the length of the shortest path.
// But we still don't have the actual path! So we have to go through the
// ENTIRE SEARCH a second time until we find it again.
fringe.push_back(uind);
while (!fringe.empty()) {
int cur = fringe.back();
// Search for cur in the curPath (check if that vertex is "gray")
bool white = true;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == cur) white = false;
}
if (white) {
// cur is an unexplored vetex ON THIS PATH.

// Update curLength (stays at 0 if curPath is empty)
if (!curPath.empty()) {
int previous = curPath.back();
curLength += costs[previous][cur] + timeCost*times[previous][cur];
}

// Add cur to the path
curPath.push_back(cur);

if (cur == vind) {
// Found a path to the destination!
if (curLength == shortest) {
// WE FOUND IT!
break; // Break out of the while loop.
}

}

// Add all cur's children to the fringe.
// Skip children that are already in curPath though!
for (int child=0; child<n; ++child) {
bool inpath = false;
for (int j=0; j<curPath.size(); ++j) {
if (curPath[j] == child) inpath = true;
}
if (!inpath && costs[cur][child] >= 0)
fringe.push_back(child);
}
}
else {
// cur has just finished being explored, so pop it off.
fringe.pop_back();
curPath.pop_back();
if (!curPath.empty()) {
int previous = curPath.back();
curLength -= costs[previous][cur] + timeCost*times[previous][cur];
}
}
}

// Now print out the actual length and path.
cout << curLength;
for (int j=0; j<curPath.size(); ++j)
cout << ' ' << names[curPath[j]];
cout << endl;
}

// Clean up memory
delete [] names;
delete [] times[0];
delete [] times;
delete [] costs[0];
delete [] costs;

return 0;
}

// Prints an error message and exits ungracefully
void error (const char* msg) {
cerr << "ERROR:" << endl << msg << endl;
exit(1);
}

// Looks up the given vertex name in the array of names,
// and returns the index of that vertex in the array.
// Uses the linearSearch algorithm for search in an unsorted array.
int lookup (const string& name, const string* names, int n) {
for (int i=0; i<n; ++i) {
if (names[i].compare(name) == 0)
return i;
}
return -1;
}
```