#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;
vector <string> v1 = {"Prague", "Helsinki", "Beijing", "Tokyo", "Jakarta","London", "New York"};
vector <int> w = {};
// A directed graph using
// adjacency list representation
class Graph {
    int V; // No. of vertices in graph
    list<int>* adj; // Pointer to an array containing adjacency lists
    list<int>* adj_weights; // Pointer to an array containing adjacency lists
 
    // A recursive function used by printAllPaths()
    void printAllPathsUtil(int, int, bool[], int[], int[], int&, int);
 
public:
    Graph(int V); // Constructor
    void addVertex(string name);
    void addEdge(int u, int v, int weight);
    void printAllPaths(int s, int d);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    adj_weights = new list<int>[V];
}
void Graph::addEdge(int u, int v, int weight)
{
    adj[u].push_back(v); // Add v to u’s list.
    adj_weights[u].push_back(weight); // Add the weight of the path as well.
}
 
// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
    // Mark all the vertices as not visited
    bool* visited = new bool[V];
    // Create an array to store paths
    int* path = new int[V];
    int* path_costs = new int[V];
    int path_index = 0; // Initialize path[] and path_costs[] as empty
 
    // Initialize all vertices as not visited
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Call the recursive helper function to print all paths
    // Note that we let cost = 0 since we don't have to move to the starting city
    printAllPathsUtil(s, d, visited, path_costs, path, path_index, 0);
}
 
// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[], int path_costs[],
                              int path[], int& path_index, int cost)
{
    // Mark the current node and store it in path[]
    visited[u] = true;
    path[path_index] = u;
    path_costs[path_index] = cost;   // Save cost of this step
    path_index++;
    int sum = 0;
    // If current vertex is same as destination, then print
    // current path[]
    if (u == d) {
        for (int i = 0; i < path_index; i++){
            sum += path_costs[i];   // Now add all the costs
            cout << v1[path[i]] << " ";
        }
        cout << endl;
        cout << "Total distance is: " << sum;
        cout << endl;
    }
    else // If current vertex is not destination
    {
        // Recur for all the vertices adjacent to current vertex
        // Now we loop over both adj and adj_weights
        list<int>::iterator i, j;
        for (i = adj[u].begin(), j = adj_weights[u].begin();
             i != adj[u].end(); ++i, ++j)
            if (!visited[*i])
                printAllPathsUtil(*i, d, visited, path_costs, path, 
                                  path_index, *j);
    }
 
    // Remove current vertex from path[] and mark it as unvisited
    path_index--;
    visited[u] = false;
}
 
// Driver program
int main()
{
    // Create a graph given in the above diagram
    Graph g(7);
       
    g.addEdge(0, 1, 1845);
    g.addEdge(0, 5, 1264);
    g.addEdge(1, 3, 7815);
    g.addEdge(2, 5, 8132); 
    g.addEdge(2, 6, 11550);
    g.addEdge(2, 3, 1303);
    g.addEdge(3, 4, 5782);
    g.addEdge(3, 6, 10838);
    g.addEdge(4, 2, 4616);
    g.addEdge(5, 3, 9566);
    g.addEdge(6, 5, 5567);
    int s = 0, d = 2;
    cout << "Following are all different paths from " << v1[s] << " to " << v1[d] << endl;
    g.printAllPaths(s, d);
 
    return 0;

}