Node Splitting

Node splitting is a graph-modeling technique commonly used in network flow to handle vertex weights or vertex capacity constraints, and also frequently used in layered graphs.

Maximum flow with vertex capacity constraints

If vertices are converted into edges, the standard solution can be applied directly.

Consider converting a capacity-constrained vertex into the following structure: two vertices $u,v$ and an edge $\left\langle u,v \right\rangle$. Vertex $u$ receives all edges that arrive at the corresponding vertex from other vertices in the original graph, while vertex $v$ emits all edges that leave the corresponding original vertex toward other vertices. Set the capacity of edge $\left\langle u,v \right\rangle$ to the capacity of the original vertex, and then apply the standard method. This is the basic idea of node splitting.

If the original graph is:

After node splitting, the graph becomes:

Shortest paths in layered graphs

Consider a layered-graph shortest-path problem in which one may traverse a path at zero cost $k$ times and wants the minimum total cost. We can use a DP-style formulation: let $\text{dis}_{i, j}$ denote the shortest path from the starting vertex to vertex $i$ after using the free-passage privilege $j$ times. Clearly, the $\text{dis}$ array can be transitioned as follows:

$\text{dis}_{i, j} = \min\{\min\{\text{dis}_{from, j - 1}\}, \min\{\text{dis}_{from,j} + w\}\}$

Here, $from$ denotes the parent of $i$, and $w$ denotes the weight of the edge just traversed. When $j - 1 \geq k$, $\text{dis}_{from, j}$=$\infty$.

In fact, this DP is equivalent to splitting every vertex into $k+1$ vertices, with each new vertex representing arrival at the original vertex after using a different number of free passages. In other words, vertex $u_i$ represents reaching vertex $i$ after using the free-passage privilege $u$ times.

struct State {    // node structure for the priority queue
  int v, w, cnt;  // cnt is the number of free-passage privileges already used

  State() {}

  State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {}

  bool operator<(const State &rhs) const { return w > rhs.w; }
};

void dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  dis[s][0] = 0;
  pq.push(State(s, 0, 0));  // reaching the start requires no free passage and has distance zero
  while (!pq.empty()) {
    const State top = pq.top();
    pq.pop();
    int u = top.v, nowCnt = top.cnt;
    if (done[u][nowCnt]) continue;
    done[u][nowCnt] = true;
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v, w = edge[i].w;
      if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt]) {  // can pass for free
        dis[v][nowCnt + 1] = dis[u][nowCnt];
        pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1));
      }
      if (dis[v][nowCnt] > dis[u][nowCnt] + w) {  // cannot pass for free
        dis[v][nowCnt] = dis[u][nowCnt] + w;
        pq.push(State(v, dis[v][nowCnt], nowCnt));
      }
    }
  }
}

int main() {
  n = read(), m = read(), k = read();
  // The code normally numbers vertices from 1 to n, but this problem uses 0 to n - 1, so adjust the indices.
  s = read() + 1, t = read() + 1;
  while (m--) {
    int u = read() + 1, v = read() + 1, w = read();
    add(u, v, w), add(v, u, w);  // this problem has undirected edges
  }
  dijkstra();
  int ans = std::numeric_limits<int>::max();  // initialize ans to the maximum int value
  for (int i = 0; i <= k; ++i)
    ans = std::min(ans, dis[t][i]);  // take the best value over all ways to reach the destination
  println(ans);
}