Subtask 1

We can model each element as a node in the graph, with a spell being modelled as a weighted bidirectional edge in the graph. The minimum total cost corresponds to the shortest path in the graph from node ~1~ to node ~N~. This can be found easily using Dijkstra's algorithm.

Subtask 2

First, let's deal with the additional fees.

Instead of a node representing an element in the graph, each node will have an additional state - the current alchemist we are visiting (or none if we are not currently visiting an alchemist). From now on, let us refer to a node as ~(y, x)~, where ~y~ represents the current element and ~x~ represents the current alchemist we are visiting (or ~-1~ if we are not visiting any alchemist). Edges from type 2 alchemists now connect the nodes ~({p_x}_i, x)~ and ~({q_x}_i, x)~. The answer to the problem is the shortest distance from ~(1, -1)~ to ~(N, -1)~.

To handle the transition between visiting different alchemists, for each alchemist ~x~, and for each element they work with ~y~, we will add a directed edge from ~(y, x)~ to ~(y, -1)~ with a weight of 0, and a directed edge from ~(y, -1)~ to ~(y, x)~ with weight ~s_x~. This works because switching from visiting alchemist ~x~ to alchemist ~z~ whilst having element ~y~ can be represented by traversing the path ~(y, x) \to (y, -1) \to (y, z)~, with the weight of the path being ~s_x~.

Now, how do we deal with type 1 alchemists?

If we add edges to the graph naively, then there will be ~\mathcal{O}((\sum_{i=1}^M k_i)^2)~ edges in the graph, which is too much.

Instead, we will use the same idea as for handling the additional fees. For each type 1 alchemist ~x~, we will create a separate auxiliary node ~(-1, x)~. For each element ~{a_x}_i~ that the alchemist works with, we will add an undirected edge between ~({a_x}_i, x)~ to ~(-1, x)~ with a weight of ~{b_x}_i~. This works because transforming element ~{a_x}_i~ to ~{a_x}_j~ is equivalent to traversing the path ~({a_x}_i, x) \to (-1, x) \to ({a_x}_j, x)~, with the weight of the path being ~{b_x}_i+{b_x}_j~.

Subtask 3

Unfortunately, having the base cost of a visit being the maximum of the values of the spells performed doesn't lend itself as easily to Dijkstra's algorithm. We need to find a way to convert the costs of paths being the maximum of edge values to addition of edge values in order for Dijkstra's algorithm to work.

For now, let us focus on a different, general graph with ~N~ nodes, where the weight of a path is maximum of the weight of its edges. How can we make this graph Dijkstra-able?

Let's consider the minimum weight path from node ~u~ to ~v~ (assuming they are in the same component). We can find this path by adding edges to the graph in increasing order by weight, until there is a path from ~u~ to ~v~. Observe that we are essentially performing Kruskal's algorithm to find the minimum spanning tree - in fact, the minimum weight path between any two nodes in the same component is simply the path between them on the minimum spanning tree (technically a minimum spanning forest).

Unfortunately, this graph is still not Dijkstra-able. Currently, in Kruskal's algorithm, when we process an edge between two different components with leaders ~u~ and ~v~, we add an edge between ~u~ and ~v~ in our union-find data structure. However, instead, we could create a new auxiliary node ~w~, and set the leaders of the components we are merging to ~w~.

How does this representation help us? To see this, assign each of the ~N~ initial nodes in the graph a value of 0. For each edge in ascending order by weight, if it connects two different components, then after creating the auxiliary node ~w~, we will assign ~w~ a value equal to the weight of the current edge we are processing in the original graph. We add directed edges from ~u~ to ~w~, from ~w~ to ~u~, from ~v~ to ~w~, and from ~w~ to ~v~. Let us call the edges from ~u~ to ~w~ and from ~v~ to ~w~ 'up edges', and the edges from ~w~ to ~u~ and from ~w~ to ~v~ 'down edges'. We then set the leaders of the two components we are merging to node ~w~ in our union-find data structure.

After this process is completed, for each component in the original graph, we will have created a tree where the leaves are the nodes in the original graph. (In fact, this tree is known as a Kruskal Reconstruction Tree.) Consider the path from node ~u~ to node ~v~ in the original graph. Let ~l~ be the lowest common ancestor of ~u~ and ~v~ in the tree. Then ~l~ is an auxiliary vertex which represents the final edge which connected the components ~u~ and ~v~ were in during Kruskal's algorithm, so the value of ~l~ is equal to the minimum weight path between ~u~ and ~v~.

For all up edges from ~a~ to ~b~, we will assign a weight equal to the value of ~b~, minus the value of ~a~. All down edges will have a weight of 0.

Now, for any two leaf nodes ~u~ and ~v~ in the tree with lowest common ancestor ~l~, the value of the path between ~u~ and ~v~ in the tree will be exactly equal to the value of ~l~, due to a telescoping sum (and the fact that node ~u~ has a value of 0). Furthermore, since Kruskal's algorithm processes edges in increasing order, for all up edges from ~a~ to ~b~, the value of ~b~ will be greater than or equal to the value of ~a~, so all edges in our resulting tree will be non-negative. This means that we can use Dijkstra's algorithm on the tree.

This algorithm is directly applicable for handling type 3 alchemists. For each alchemist, we will simply build the Kruskal Reconstruction Tree as described above (technically it is a Kruskal Reconstruction Forest). Then, our final answer can still be computed via Dijkstra's algorithm.