pb10

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

struct Barrier {
  int to;
  int cost;
} * b;

struct Solution {
  int node;
  int newBarrierNode;
};

Solution *sol, *tmpsol;
int **a, n, mincost = 999999;
bool *v;

void init(int n);

void dfs(int k, int len, int cost, int end);

int main() {
  freopen("in.txt", "r", stdin);

  int m, node1, node2, cost, start, end, to;

  scanf("%d %d %d %d", &n, &m, &start, &end);

  init(n);

  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &node1, &node2, &cost);

    a[node1][node2] = a[node2][node1] = cost;
  }

  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &to, &cost);

    b[i] = {to, cost};
  }

  v[start] = 1;
  tmpsol[0].node = start;

  dfs(start, 1, 0, end);

  if (!sol[0].node) {
    printf("0\n"); // no solution found
  } else {
    int i = 0;

    while (sol[i].node) {
      printf("%d ", sol[i++].node);
    }
    printf("\n");
    for (int j = 0; j < i; j++) {
      printf("%d ", sol[j].newBarrierNode);
    }
    printf("\n");
  }

  return 0;
}

void init(int n) {
  a = (int **)malloc(sizeof(int *) * (n + 1));

  for (int i = 0; i <= n; i++) {
    a[i] = (int *)malloc(sizeof(int) * (n + 1));
  }

  b = (Barrier *)malloc(sizeof(Barrier) * (n + 1));

  sol = (Solution *)malloc(sizeof(Solution) * n);
  tmpsol = (Solution *)malloc(sizeof(Solution) * n);

  v = (bool *)malloc(sizeof(bool) * (n + 1));
}

void dfs(int k, int len, int cost, int end) {
  if (k == end) {
    if (cost < mincost) {
      // printf("-- Found new minimal solution (old: %d, new: %d) --\n   ",
      // mincost, cost);
      mincost = cost;
      for (int i = 0; i < n; i++) {
        // printf("%d ", tmpsol[i].node);
        sol[i] = tmpsol[i];
      }
      // printf("\n\n");
    }
  } else {
    for (int i = 1; i <= n; i++) {
      if (a[k][i] && !v[i]) {
        // printf("Found node %d that connects to %d\n", i, k);
        // barrier can be from k to i
        if (b[k].to == i) {
          // printf("Found barrier from node %d to %d\n", k, i);
          // search for another highway to move the barrier to
          for (int j = 1; j <= n; j++) {
            if (a[k][j] && i != j && !v[j]) {
              // printf("Moving barrier of %d from %d to %d\n", k, i, j);
              b[k].to = j;
              v[i] = 1;
              tmpsol[len].node = i;
              tmpsol[len - 1].newBarrierNode = j;

              // printf("Entering dfs\n\n");
              dfs(i, len + 1, cost + b[k].cost + a[k][i], end);

              // printf("Moving barrier of %d back from %d to %d\n", k, j, i);
              b[k].to = i;
              tmpsol[len].node = 0;
              tmpsol[len - 1].newBarrierNode = 0;
              v[i] = 0;
            }
          }
        }
        // or it can be from i to k
        else if (b[i].to == k) {
          // printf("Found barrier from node %d to %d\n", i, k);
          // search for another highway to move the barrier to
          for (int j = 1; j <= n; j++) {
            if (a[i][j] && k != j && !v[j]) {
              // printf("Moving barrier of %d from %d to %d\n", i, k, j);
              b[i].to = j;
              v[i] = 1;
              tmpsol[len].node = i;
              tmpsol[len - 1].newBarrierNode = j;

              // printf("Entering dfs\n\n");
              dfs(i, len + 1, cost + b[i].cost + a[k][i], end);

              // printf("Moving barrier of %d back from %d to %d\n", i, j, k);
              b[i].to = k;
              tmpsol[len].node = 0;
              tmpsol[len - 1].newBarrierNode = 0;
              v[i] = 0;
            }
          }
        }
        // or there is no barrier
        else {
          v[i] = 1;
          tmpsol[len].node = i;
          tmpsol[len - 1].newBarrierNode = 0;

          // printf("Entering dfs\n\n");
          dfs(i, len + 1, cost + a[k][i], end);

          tmpsol[len].node = 0;
          tmpsol[len - 1].newBarrierNode = 0;
          v[i] = 0;
        }
      }
    }
  }
}