commit 1d2c19f97d65f87b641e11127c0853f6e3fb5b7c
parent 7cb9043ca3ec67591aa4ee1d904fe2b4d31cf79b
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 27 Jan 2026 09:18:44 -0700
3650. minimum cost path with edge reversals
Diffstat:
2 files changed, 200 insertions(+), 0 deletions(-)
diff --git a/min_cost_path_edge_rev.c b/min_cost_path_edge_rev.c
@@ -0,0 +1,148 @@
+// 3650. Minimum Cost Path with Edge Reversals
+#include "leetcode.h"
+
+/*
+ * you are given a directed, weighted graph with 'n' nodes labeled from 0 to 'n
+ * - 1', and an array 'edges' where 'edges[i] =[ui, vi, wi]' represents a
+ * directed edge from node 'ui' to node 'vi' with cost 'wi'. each node 'ui' has
+ * a switch that can be used at most once: when you arrive at 'ui' and have not
+ * yet its switch, you may activate it on one of its incoming edges 'vi -> ui'
+ * reverse that edge to 'ui -> vi' and immediately traverse it. the reversal is
+ * only valid for that single move, and using a reversed edge costs '2 * wi'.
+ * return the minimum cost to travel from node 0 to node 'n - 1'. if it is not
+ * possible, return -1.
+ */
+
+struct edge {
+ int to;
+ int weight;
+ struct edge *next;
+};
+
+struct heap_node {
+ int node;
+ int cost;
+};
+
+struct min_heap {
+ struct heap_node *data;
+ int size;
+ int capacity;
+};
+
+struct min_heap *min_heap_init(int capacity) {
+ struct min_heap *obj = (struct min_heap *)malloc(sizeof(struct min_heap));
+ obj->data = (struct heap_node *)malloc(capacity * sizeof(struct heap_node));
+ obj->size = 0;
+ obj->capacity = capacity;
+ return obj;
+}
+
+void swap(struct heap_node *a, struct heap_node *b) {
+ struct heap_node tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+void min_heap_push(struct min_heap *obj, int node, int cost) {
+ if (obj->size == obj->capacity)
+ return;
+ int idx = obj->size;
+ obj->data[idx].node = node;
+ obj->data[idx].cost = cost;
+ while (idx > 0 && obj->data[(idx - 1) / 2].cost > obj->data[idx].cost) {
+ swap(&obj->data[(idx - 1) / 2], &obj->data[idx]);
+ idx = (idx - 1) / 2;
+ }
+}
+
+struct heap_node min_heap_pop(struct min_heap *obj) {
+ struct heap_node root = obj->data[0];
+ obj->data[0] = obj->data[--obj->size];
+ int idx = 0;
+ while (2 * idx + 1 < obj->size) {
+ int smallest = idx, left = 2 * idx + 1, right = 2 * idx + 2;
+ if (left < obj->size && obj->data[left].cost < obj->data[smallest].cost)
+ smallest = left;
+ if (right < obj->size && obj->data[right].cost < obj->data[smallest].cost)
+ smallest = right;
+ if (smallest != idx) {
+ swap(&obj->data[idx], &obj->data[smallest]);
+ idx = smallest;
+ } else
+ break;
+ }
+ return root;
+}
+
+bool is_empty(struct min_heap *obj) { return !obj->size; }
+
+void add_edge(struct edge **adj, int u, int v, int w) {
+ struct edge *obj = (struct edge *)malloc(sizeof(struct edge));
+ obj->to = v;
+ obj->weight = w;
+ obj->next = adj[u];
+ adj[u] = obj;
+}
+
+int minCost(int n, int **edges, int edgesSize, int *edgesColSize) {
+ struct edge **adj = (struct edge **)calloc(n, sizeof(struct edge *));
+ for (int i = 0; i < edgesSize; i++) {
+ int u = edges[i][0];
+ int v = edges[i][1];
+ int w = edges[i][2];
+ add_edge(adj, u, v, w);
+ add_edge(adj, v, u, w * 2);
+ }
+ int *dist = (int *)malloc(n * sizeof(int)), ans = -1;
+ for (int i = 0; i < n; i++)
+ dist[i] = INT_MAX;
+ struct min_heap *pq = min_heap_init(edgesSize * 4 + 1000);
+ dist[0] = 0;
+ min_heap_push(pq, 0, 0);
+ while (!is_empty(pq)) {
+ struct heap_node top = min_heap_pop(pq);
+ int u = top.node, d = top.cost;
+ if (u == n - 1) {
+ ans = d;
+ break;
+ }
+ if (d > dist[u])
+ continue;
+ struct edge *curr = adj[u];
+ while (curr) {
+ int v = curr->to, w = curr->weight;
+ if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
+ dist[v] = dist[u] + w;
+ min_heap_push(pq, v, dist[v]);
+ }
+ curr = curr->next;
+ }
+ }
+ free(dist);
+ free(pq->data);
+ free(pq);
+ for (int i = 0; i < n; i++) {
+ struct edge *curr = adj[i];
+ while (curr) {
+ struct edge *tmp = curr;
+ curr = curr->next;
+ free(tmp);
+ }
+ }
+ free(adj);
+ return ans;
+}
+
+int main() {
+ int e1i[4][3] = {{0, 1, 3}, {3, 1, 1}, {2, 3, 4}, {0, 2, 2}};
+ int e2i[4][3] = {{0, 2, 1}, {2, 1, 1}, {1, 3, 1}, {2, 3, 3}};
+ struct two_d_arr *e1 =
+ two_d_arr_init(ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ struct two_d_arr *e2 =
+ two_d_arr_init(ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ printf("%d\n", minCost(4, e1->arr, e1->row_size, e1->col_size)); // expect: 5
+ printf("%d\n", minCost(4, e2->arr, e2->row_size, e2->col_size)); // expect: 3
+ two_d_arr_free(e1);
+ two_d_arr_free(e2);
+}
diff --git a/min_cost_path_edge_rev.py b/min_cost_path_edge_rev.py
@@ -0,0 +1,52 @@
+# 3650. Minimum Cost Path with Edge Reversals
+import heapq
+
+"""
+you are given a directed, weighted graph with 'n' nodes labeled from 0 to 'n
+- 1', and an array 'edges' where 'edges[i] =[ui, vi, wi]' represents a
+directed edge from node 'ui' to node 'vi' with cost 'wi'. each node 'ui' has
+a switch that can be used at most once: when you arrive at 'ui' and have not
+yet its switch, you may activate it on one of its incoming edges 'vi -> ui'
+reverse that edge to 'ui -> vi' and immediately traverse it. the reversal is
+only valid for that single move, and using a reversed edge costs '2 * wi'.
+return the minimum cost to travel from node 0 to node 'n - 1'. if it is not
+possible, return -1.
+"""
+
+
+class Solution(object):
+ def dijkstra(self, n):
+ inf = float("inf")
+ vis = [False] * n
+ dist = [inf] * n
+ pq = [(0, 0)]
+ dist[0] = 0
+ while pq:
+ du, u = heapq.heappop(pq)
+ if vis[u]:
+ continue
+ vis[u] = True
+ for v, w in self.g[u]:
+ nd = du + w
+ if nd < dist[v]:
+ dist[v] = nd
+ heapq.heappush(pq, (nd, v))
+ return -1 if dist[n - 1] == inf else dist[n - 1]
+
+ def minCost(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ self.g = [[] for _ in range(n)]
+ for u, v, w in edges:
+ self.g[u].append((v, w))
+ self.g[v].append((u, w * 2))
+ return self.dijkstra(n)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCost(n=4, edges=[[0, 1, 3], [3, 1, 1], [2, 3, 4], [0, 2, 2]]))
+ print(obj.minCost(n=4, edges=[[0, 2, 1], [2, 1, 1], [1, 3, 1], [2, 3, 3]]))
