Directed weighted graphs are fundamental data structures in computer science, used to model relationships where connections have both direction and a specific cost or value. A common and efficient way to represent such graphs, especially when they are sparse (i.e., have relatively few edges compared to the maximum possible), is using an adjacency list.

An adjacency list representation stores each vertex and a list of its neighbors. For a weighted graph, each entry in the neighbor list also includes the weight associated with the edge. For a directed graph, an edge from vertex A to vertex B (A → B) means B is in A's adjacency list, but A is not necessarily in B's list unless there's also an edge B → A.

Data Structure Design

To implement a directed weighted graph with character-based vertex labels, we can use the following components:

• A mechanism to store the actual character labels of vertices.
• A mapping from these character labels to integer indices, which are easier to work with for array/vector access.
• A primary adjacency list structure, typically a vector of vectors. Each inner vector represents the list of outgoing edges from a specific vertex, storing pairs of (neighbor index, edge weight).

A C++ class can encapsulate these elements, providing methods for graph initialization and edge addition.

Input and Output Specifications

Input Format:

The first line contains two integers, N (number of vertices) and M (number of edges), separated by a space.

The next line contains N character labels for the vertices, separated by spaces or newlines.

Following this, M lines each describe an edge, containing the source vertex label, the destination vertex label, and the integer weight, all separated by spaces.

Output Format:

If the input data is valid, the program should print the adjacency list representation. Each line corresponds to a vertex. It starts with the vertex label, followed by a sequence of its adjacent neighbors. Each neighbor is represented by "->neighbor_index weight", where 'neighbor_index' is the 0-based integer index of the adjacent vertex and 'weight' is the edge's weight. Neighbor entries are separated by spaces. Lines are separated by newlines, except for the last line.

Example Output:

a->2 1->1 1
b
c->3 1
d->0 1

Error Conditions:

• If N (number of vertices) is 0, output "error".
• If N is 1 and M (number of edges) is greater than 1, output "error".
• If any specified source or destination vertex label during edge creation does not exist, output "error".

C++ Implementation Example

The following C++ code demonstrates the implementation using std::vector and std::map for efficient storage and lookup. Edges are prepended to the adjacency list for output order consistency with typical problem requirements.

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility> // For std::pair
#include <stdexcept> // For std::runtime_error

/**
 * @brief Represents a directed weighted graph using an adjacency list.
 */
class DirectedWeightedGraph {
private:
    int totalVertices; ///< Total number of vertices in the graph.
    std::vector<char> vertexLabels; ///< Stores the character labels for each vertex, indexed by their integer ID.
    std::map<char, int> labelToIndexMap; ///< Maps character labels to their corresponding integer indices (0-based).
    std::vector<std::vector<std::pair<int, int>>> adjacencyLists; ///< Adjacency list: each entry is a list of {neighbor_index, weight}.

    /**
     * @brief Retrieves the integer index for a given character vertex label.
     * @param label The character label of the vertex.
     * @return The integer index of the vertex, or -1 if the label is not found.
     */
    int getVertexIndex(char label) const {
        auto it = labelToIndexMap.find(label);
        if (it != labelToIndexMap.end()) {
            return it->second;
        }
        return -1; // Vertex label not found
    }

public:
    /**
     * @brief Default constructor for the graph.
     */
    DirectedWeightedGraph() : totalVertices(0) {}

    /**
     * @brief Initializes the graph with a specified number of vertices and their labels.
     * @param count The number of vertices (N).
     * @param labels A vector of character labels for the vertices.
     */
    void initializeGraphVertices(int count, const std::vector<char>& labels) {
        totalVertices = count;
        vertexLabels = labels;
        adjacencyLists.resize(totalVertices);
        for (int i = 0; i < totalVertices; ++i) {
            labelToIndexMap[vertexLabels[i]] = i;
        }
    }

    /**
     * @brief Adds a directed weighted edge to the graph.
     *        New edges are prepended to the adjacency list for consistent output order.
     * @param sourceLabel The character label of the source vertex.
     * @param destLabel The character label of the destination vertex.
     * @param weight The weight of the edge.
     * @throws std::runtime_error if either source or destination vertex label is invalid.
     */
    void connectVertices(char sourceLabel, char destLabel, int weight) {
        int u = getVertexIndex(sourceLabel);
        int v = getVertexIndex(destLabel);

        if (u == -1 || v == -1) {
            throw std::runtime_error("Error: Invalid vertex label encountered when adding edge.");
        }
        // Prepend the new edge to the adjacency list of the source vertex.
        adjacencyLists[u].insert(adjacencyLists[u].begin(), {v, weight});
    }

    /**
     * @brief Prints the adjacency list representation of the graph to standard output.
     */
    void displayGraphAdjacencyList() const {
        for (int i = 0; i < totalVertices; ++i) {
            std::cout << vertexLabels[i];
            for (const auto& edge : adjacencyLists[i]) {
                // Format: ->neighbor_index weight
                std::cout << "->" << edge.first << " " << edge.second;
            }
            // Add a newline character after each vertex's list, except for the last one.
            if (i < totalVertices - 1) {
                std::cout << std::endl;
            }
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false); // Optimize C++ streams
    std::cin.tie(NULL); // Untie cin from cout

    int N, M; // N: number of vertices, M: number of edges
    std::cin >> N >> M;

    // Handle specified error conditions based on N and M values.
    if (N == 0 || (N == 1 && M > 1)) {
        std::cout << "error"; // No newline as per problem description
        return 0;
    }

    DirectedWeightedGraph graph;
    std::vector<char> labels(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> labels[i];
    }
    graph.initializeGraphVertices(N, labels);

    for (int i = 0; i < M; ++i) {
        char source, destination;
        int edgeWeight;
        std::cin >> source >> destination >> edgeWeight;
        try {
            graph.connectVertices(source, destination, edgeWeight);
        } catch (const std::runtime_error& e) {
            // Catch error if vertex labels are invalid during edge addition.
            std::cout << "error"; // No newline as per problem description
            return 0;
        }
    }

    graph.displayGraphAdjacencyList();

    return 0;
}