2-d

#include <stdio.h>
#include <malloc.h>
#define N 301
int array[N][N] = {0}, d[N][N] = {0}, v[N] = {0};
int MAX = 2147483647;

struct list {
    int data;
    struct list *next;
};

typedef struct stack {
    struct list *top;
} Stack;

Stack *create() {
    Stack *S;
    S = (Stack *) malloc(sizeof(Stack));
    S->top = NULL;
    return S;
}

int pop(Stack *S) {
    int a;
    struct list *p;
    p = S->top;
    a = p->data;
    S->top = p->next;
    free(p);
    return a;
}

void push(Stack *S, int a) {
    struct list *p;
    p = (struct list *) malloc(sizeof(struct list));
    p->data = a;
    p->next = S->top;
    S->top = p;
}

int main() {
    freopen("input.txt", "r", stdin);
    int n, m, p, k;
    scanf("%d%d%d%d", &n, &m, &p, &k);
    int transfer_rate, s_1, s_2;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &s_1, &s_2, &transfer_rate);
        if (array[s_1][s_2] == 0 || array[s_1][s_2] > transfer_rate) {
            array[s_1][s_2] = transfer_rate;
            array[s_2][s_1] = transfer_rate;
        }
    }

    int finish, weight, count, min_index, min, temp;
    Stack *stack = create();

    for (int j = 0; j < (n + 1); ++j) {
        for (int i = 1; i < (n + 1); ++i) {
            d[j][i] = MAX;
            v[i] = 1;
        }
        d[j][j] = 0;
        do {
            min_index = MAX;
            min = MAX;
            for (int i = 1; i < (n + 1); ++i) {
                if ((v[i] == 1) && (d[j][i] < min)) {
                    min = d[j][i];
                    min_index = i;
                }
            }
            if (min_index != MAX) {
                for (int i = 1; i < (n + 1); ++i) {
                    if (array[min_index][i] > 0) {
                        temp = min + array[min_index][i];
                        if (temp < d[j][i]) {
                            d[j][i] = temp;
                        }
                    }
                }
                v[min_index] = 0;
            }
        } while (min_index < MAX);
    }

    int start, final;
    for (int j = 0; j < p; ++j) {
        scanf("%d %d", &start, &final);
        printf("%d ", d[start][final]);
        finish = final;
        weight = d[start][finish];
        count = 1;
        while (finish != start) {
            for (int i = 1; i < (n + 1); ++i)
                if (array[i][finish] != 0) {
                    temp = weight - array[i][finish];
                    if (temp == d[start][i]) {
                        weight = temp;
                        finish = i;
                        ++count;
                        push(stack, i);
                    }
                }
        }
        printf("%d ", count);
        while (stack->top != NULL) printf("%d ", pop(stack));
        printf("%d", final);
        printf("\n");
    }

    for (int j = 0; j < k; ++j) {
        scanf("%d %d", &start, &final);
        printf("%d\n", d[start][final]);
    }

    return 0;
}