diff options
author | Jack Sangdahl <[email protected]> | 2024-07-28 17:41:01 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-28 17:41:01 -0600 |
commit | 09570f171a5c9a6540cd7350e0fed3b71b1472ce (patch) | |
tree | 39704dd971add336f2f8ee6e9d562840bf50f1c1 | |
parent | 9b1687331bb6385e4ae676b1be5482d3c2156fd4 (diff) | |
download | leetcode-09570f171a5c9a6540cd7350e0fed3b71b1472ce.tar.gz leetcode-09570f171a5c9a6540cd7350e0fed3b71b1472ce.zip |
2045. second minimum time to reach destination
-rw-r--r-- | second_min_time_dest.c | 186 | ||||
-rw-r--r-- | second_min_time_dest.py | 56 |
2 files changed, 242 insertions, 0 deletions
diff --git a/second_min_time_dest.c b/second_min_time_dest.c new file mode 100644 index 0000000..02852ea --- /dev/null +++ b/second_min_time_dest.c @@ -0,0 +1,186 @@ +// 2045. Second Minimum Time to Reach Destination +#include "leetcode.h" + +/* + * a city is represented as a bi directional connected graph with 'n' vertices + * where each vertex is labeled from 1 to 'n' inclusively. the edges in the + * graph are represented as a 2d integer array 'edges' where each 'edges[i] = + * [ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'. + * every vertex pair is connected by at most one edge, and no vertex has an edge + * to itself. the time taken to traverse any edge is 'time' minutes. each vertex + * has a traffic signal which changes its colour from green to red and vice + * versa every 'change' minutes. all signals change at the same time. you can + * entre a vertex at any time, but can leave a vertex only when the signal is + * green. you cannot wait at a vertex if the signal is green. + */ + +struct state { + int node; + int time; +}; + +struct min_heap { + struct state *data; + int size; + int capacity; +}; + +void swap(struct state *a, struct state *b) { + struct state tmp = *a; + *a = *b; + *b = tmp; +} + +struct min_heap *create_min_heap(int capacity) { + struct min_heap *heap = (struct min_heap *)malloc(sizeof(struct min_heap)); + heap->data = (struct state *)malloc(capacity * sizeof(struct state)); + heap->size = 0; + heap->capacity = capacity; + return heap; +} + +void min_heapify(struct min_heap *heap, int idx) { + int smallest = idx, left = 2 * idx + 1, right = 2 * idx + 2; + if (left < heap->size && heap->data[left].time < heap->data[smallest].time) + smallest = left; + if (right < heap->size && heap->data[right].time < heap->data[smallest].time) + smallest = right; + if (smallest != idx) { + swap(&heap->data[idx], &heap->data[smallest]); + min_heapify(heap, smallest); + } +} + +struct state extract_min(struct min_heap *heap) { + if (heap->size <= 0) + return (struct state){-1, -1}; + if (heap->size == 1) { + heap->size--; + return heap->data[0]; + } + struct state root = heap->data[0]; + heap->data[0] = heap->data[heap->size - 1]; + heap->size--; + min_heapify(heap, 0); + return root; +} + +void insert_min_heap(struct min_heap *heap, struct state k) { + if (heap->size == heap->capacity) { + heap->capacity *= 2; + heap->data = (struct state *)realloc(heap->data, + heap->capacity * sizeof(struct state)); + } + heap->size++; + int i = heap->size - 1; + heap->data[i] = k; + while (i && heap->data[(i - 1) / 2].time > heap->data[i].time) { + swap(&heap->data[i], &heap->data[(i - 1) / 2]); + i = (i - 1) / 2; + } +} + +void free_min_heap(struct min_heap *heap) { + free(heap->data); + free(heap); +} + +struct node { + int val; + struct node *next; +}; + +struct graph { + struct node **heads; + int *sizes; + int size; +}; + +struct graph *create_graph(int n) { + struct graph *g = (struct graph *)malloc(sizeof(struct graph)); + g->heads = (struct node **)malloc((n + 1) * sizeof(struct node *)); + g->sizes = (int *)calloc(n + 1, sizeof(int)); + g->size = n; + for (int i = 0; i <= n; i++) + g->heads[i] = NULL; + return g; +} + +void add_edges(struct graph *g, int u, int v) { + struct node *n = (struct node *)malloc(sizeof(struct node)); + n->val = v; + n->next = g->heads[u]; + g->heads[u] = n; + n = (struct node *)malloc(sizeof(struct node)); + n->val = u; + n->next = g->heads[v]; + g->heads[v] = n; + g->sizes[u]++; + g->sizes[v]++; +} + +void free_graph(struct graph *g) { + for (int i = 0; i <= g->size; i++) { + struct node *head = g->heads[i]; + while (head) { + struct node *tmp = head; + head = head->next; + free(tmp); + } + } + free(g->heads); + free(g->sizes); + free(g); +} + +int secondMinimum(int n, int **edges, int edgesSize, int *edgesColSize, + int time, int change) { + struct graph *g = create_graph(n); + for (int i = 0; i < edgesSize; i++) + add_edges(g, edges[i][0], edges[i][1]); + int *min_time = (int *)malloc((n + 1) * sizeof(int)); + int *second_min_time = (int *)malloc((n + 1) * sizeof(int)); + for (int i = 0; i <= n; i++) { + min_time[i] = INT_MAX; + second_min_time[i] = INT_MAX; + } + struct min_heap *pq = create_min_heap(edgesSize * 2); + insert_min_heap(pq, (struct state){1, 0}); + min_time[1] = 0; + while (pq->size) { + struct state curr = extract_min(pq); + int curr_node = curr.node; + int curr_time = curr.time; + struct node *neighbour_node = g->heads[curr_node]; + while (neighbour_node) { + int neighbour = neighbour_node->val, wait_time = 0; + if ((curr_time / change) % 2 == 1) + wait_time = change = (curr_time % change); + int next_time = curr_time + time + wait_time; + if (next_time < min_time[neighbour]) { + second_min_time[neighbour] = min_time[neighbour]; + min_time[neighbour] = next_time; + insert_min_heap(pq, (struct state){neighbour, next_time}); + } else if (next_time > min_time[neighbour] && + next_time < second_min_time[neighbour]) { + second_min_time[neighbour] = next_time; + insert_min_heap(pq, (struct state){neighbour, next_time}); + } + neighbour_node = neighbour_node->next; + } + } + int ans = second_min_time[n]; + free(min_time), free(second_min_time); + free_min_heap(pq); + free_graph(g); + return ans; +} + +int main() { + int e1[5][2] = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}}, e2[1][2] = {{1, 2}}; + int ecs1 = 5, ecs2 = 1; + printf("%d\n", secondMinimum(5, (int **)e1, ARRAY_SIZE(e1), &ecs1, 3, + 5)); // expect: 13 + printf("%d\n", secondMinimum(2, (int **)e2, ARRAY_SIZE(e2), &ecs2, 3, + 2)); // expect: 11 +} diff --git a/second_min_time_dest.py b/second_min_time_dest.py new file mode 100644 index 0000000..adf08da --- /dev/null +++ b/second_min_time_dest.py @@ -0,0 +1,56 @@ +# 2045. Second Minimum Time to Reach destination +from collections import defaultdict +import heapq +from math import ceil + +""" +a city is represented as a bi directional connected graph with 'n' vertices +where each vertex is labeled from 1 to 'n' inclusively. the edges in the +graph are represented as a 2d integer array 'edges' where each 'edges[i] = +[ui, vi]' denotes a bi directional edge between vertex 'ui' and vertex 'vi'. +every vertex pair is connected by at most one edge, and no vertex has an edge +to itself. the time taken to traverse any edge is 'time' minutes. each vertex +has a traffic signal which changes its colour from green to red and vice +versa every 'change' minutes. all signals change at the same time. you can +entre a vertex at any time, but can leave a vertex only when the signal is +green. you cannot wait at a vertex if the signal is green. +""" + + +class Solution(object): + def secondMinimum(self, n, edges, time, change): + """ + :type n: int + :type edges: List[List[int]] + :type time: int + :type change: int + :rtype: int + """ + d = [[] for _ in range(n + 1)] + d[1] = [0] + g, heap = defaultdict(list), [(0, 1)] + for a, b in edges: + g[a] += [b] + g[b] += [a] + while heap: + min_dist, idx = heapq.heappop(heap) + if idx == n and len(d[n]) == 2: + return max(d[n]) + for neib in g[idx]: + if (min_dist // change) % 2 == 0: + cand = min_dist + time + else: + cand = ceil(min_dist / (2 * change)) * (2 * change) + time + if not d[neib] or (len(d[neib]) == 1 and d[neib] != [cand]): + d[neib] += [cand] + heapq.heappush(heap, (cand, neib)) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.secondMinimum( + n=5, edges=[[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]], time=3, change=5 + ) + ) + print(obj.secondMinimum(n=2, edges=[[1, 2]], time=3, change=2)) |