[알고리즘] C 코드트리 투어

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour/submissions?page=1&pageSize=5

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 2000
#define MAX_EDGES 10000
#define MAX_PRODUCTS 30001
#define INF 1000000000

typedef struct Edge {
    int to;
    int weight;
    struct Edge *next;
} Edge;

Edge *graph[MAX_NODES];

typedef struct Product {
    int id;
    int revenue;
    int dest;
    int cost_id;
} Product;

Product products[MAX_PRODUCTS];
int product_exists[MAX_PRODUCTS];

int n;

int dist[MAX_NODES];

typedef struct DijkstraNode {
    int dist;
    int node;
} DijkstraNode;

DijkstraNode dijkstra_heap[MAX_EDGES + MAX_NODES];
int dijkstra_heap_size;

void dijkstra_heap_swap(int i, int j) {
    DijkstraNode temp = dijkstra_heap[i];
    dijkstra_heap[i] = dijkstra_heap[j];
    dijkstra_heap[j] = temp;
}

void dijkstra_heapify_up(int index) {
    while (index > 1 && dijkstra_heap[index].dist < dijkstra_heap[index / 2].dist) {
        dijkstra_heap_swap(index, index / 2);
        index /= 2;
    }
}

void dijkstra_heapify_down(int index) {
    int smallest = index;
    int left = index * 2;
    int right = index * 2 + 1;

    if (left <= dijkstra_heap_size && dijkstra_heap[left].dist < dijkstra_heap[smallest].dist) {
        smallest = left;
    }
    if (right <= dijkstra_heap_size && dijkstra_heap[right].dist < dijkstra_heap[smallest].dist) {
        smallest = right;
    }
    if (smallest != index) {
        dijkstra_heap_swap(index, smallest);
        dijkstra_heapify_down(smallest);
    }
}

void dijkstra_heap_push(DijkstraNode node) {
    dijkstra_heap_size++;
    dijkstra_heap[dijkstra_heap_size] = node;
    dijkstra_heapify_up(dijkstra_heap_size);
}

DijkstraNode dijkstra_heap_pop() {
    DijkstraNode top = dijkstra_heap[1];
    dijkstra_heap[1] = dijkstra_heap[dijkstra_heap_size];
    dijkstra_heap_size--;
    dijkstra_heapify_down(1);
    return top;
}

void compute_shortest_paths(int start) {
    int i;
    for (i = 0; i < n; i++) {
        dist[i] = INF;
    }
    dist[start] = 0;

    dijkstra_heap_size = 0;
    dijkstra_heap_push((DijkstraNode){0, start});

    int max_count = n;
    while (dijkstra_heap_size > 0 && max_count > 0) {
        DijkstraNode current = dijkstra_heap_pop();
        int u = current.node;
        if (dist[u] < current.dist) {
            continue;
        }
        Edge *e = graph[u];
        while (e != NULL) {
            int v = e->to;
            int w = e->weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                dijkstra_heap_push((DijkstraNode){dist[v], v});
            }
            e = e->next;
        }
        max_count--;
    }
}

typedef struct HeapNode {
    int profit;
    int id;
} HeapNode;

HeapNode heap[MAX_PRODUCTS];
int heap_size;

void heap_swap(int i, int j) {
    HeapNode temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

void heapify_up(int index) {
    while (index > 1) {
        if (heap[index].profit > heap[index / 2].profit || (heap[index].profit == heap[index / 2].profit && heap[index].id < heap[index / 2].id)) {
            heap_swap(index, index / 2);
            index /= 2;
        } else {
            break;
        }
    }
}

void heapify_down(int index) {
    while (1) {
        int largest = index;
        int left = index * 2;
        int right = index * 2 + 1;

        if (left <= heap_size && 
                (heap[left].profit > heap[largest].profit ||
                 (heap[left].profit == heap[largest].profit && heap[left].id < heap[largest].id))) {
            largest = left;
        }
        if (right <= heap_size &&
                (heap[right].profit > heap[largest].profit ||
                 (heap[right].profit == heap[largest].profit && heap[right].id < heap[largest].id))) {
            largest = right;
        }

        if (largest != index) {
            heap_swap(index, largest);
            index = largest;
        } else {
            break;
        }
    }
}

void heap_push(HeapNode node) {
    heap_size++;
    heap[heap_size] = node;
    heapify_up(heap_size);
}

HeapNode heap_pop() {
    HeapNode top = heap[1];
    heap[1] = heap[heap_size];
    heap_size--;
    heapify_down(1);
    return top;
}

void heap_clear() {
    heap_size = 0;
}

int main() {
    int Q;
    scanf("%d", &Q);

    char buffer[500000];
    int departure_city = 0;

    int first_command_read = 0;
    while (!first_command_read) {
        if (fgets(buffer, sizeof(buffer), stdin) == NULL) {
            break;
        }
        char *token = strtok(buffer, " \n");
        if (token == NULL || strcmp(token, "100") != 0) {
            continue;
        }
        first_command_read = 1;

        n = atoi(strtok(NULL, " \n"));
        int m = atoi(strtok(NULL, " \n"));

        int i;
        for (i = 0; i < n; i++) {
            graph[i] = NULL;
        }

        int edge_count = 0;
        while (edge_count < m) {
            char *v_str = strtok(NULL, " \n");
            if (v_str == NULL) {
                if (fgets(buffer, sizeof(buffer), stdin) == NULL) {
                    break;
                }
                v_str = strtok(buffer, " \n");
            }
            int v = atoi(v_str);
            int u = atoi(strtok(NULL, " \n"));
            int w = atoi(strtok(NULL, " \n"));

            Edge *e = (Edge *) malloc(sizeof(Edge));
            e->to = u;
            e->weight = w;
            e->next = graph[v];
            graph[v] = e;

            e = (Edge *)malloc(sizeof(Edge));
            e->to = v;
            e->weight = w;
            e->next = graph[u];
            graph[u] = e;

            edge_count++;
        }
    }

    compute_shortest_paths(departure_city);

    memset(product_exists, 0, sizeof(product_exists));

    int commands_processed = 1;
    while (commands_processed < Q) {
        if (fgets(buffer, sizeof(buffer), stdin) == NULL) {
            break;
        }

        char *ptr = buffer;
        while (*ptr == ' ' || *ptr == '\n') {
            ptr++;
        }
        if (*ptr == '\0') {
            continue;
        }

        char *cmd_str = strtok(ptr, " \n");
        if (cmd_str == NULL) {
            continue;
        }

        int cmd = atoi(cmd_str);
        commands_processed++;

        if (cmd == 200) {
            int id = atoi(strtok(NULL, " \n"));
            int revenue = atoi(strtok(NULL, " \n"));
            int dest = atoi(strtok(NULL, " \n"));

            int cost_id = dist[dest];
            products[id].id = id;
            products[id].revenue = revenue;
            products[id].dest = dest;
            products[id].cost_id = cost_id;
            product_exists[id] = 1;

            int profit = revenue - cost_id;
            if (cost_id != INF && profit >= 0) {
                heap_push((HeapNode){profit, id});
            }
        } else if (cmd == 300) {
            int id = atoi(strtok(NULL, " \n"));
            if (product_exists[id]) {
                product_exists[id] = 0;
            }
        } else if (cmd == 400) {
            int sold = 0;
            while (heap_size > 0) {
                HeapNode top = heap_pop();
                int id = top.id;
                if (!product_exists[id]) {
                    continue;
                }
                product_exists[id] = 0;
                printf("%d\n", id);
                sold = 1;
                break;
            }
            if (!sold) {
                printf("-1\n");
            }
        } else if (cmd == 500) {
                int s = atoi(strtok(NULL, " \n"));
                departure_city = s;
                compute_shortest_paths(departure_city);

                heap_clear();
                int id;
                for (id = 1; id < MAX_PRODUCTS; id++) {
                    if (product_exists[id]) {
                        Product *p = &products[id];
                        int dest = p->dest;
                        int cost_id = dist[dest];
                        p->cost_id = cost_id;
                        int profit = p->revenue - cost_id;
                        if (cost_id != INF && profit >= 0) {
                            heap_push((HeapNode){profit, id});
                        }
                    }
                }
            } else {
                continue;
            }
        }

        int i;
        for (i = 0; i < n; i++) {
            Edge *e = graph[i];
            while (e != NULL) {
                Edge *temp = e;
                e = e->next;
                free(temp);
            }
        }

        return 0;
}