#include "Annalib.h"
#define N 300
#define C 5
#define INF 0x3f3f3f3f3f3f3f3fLL
static long long min(long long a, long long b) { return a < b ? a : b; }
void Anna(int n, int m, int *uu, int *vv, long long *ww, int q, int *ss, int *tt, int c, int *hh) {
long long ww_[N][N], dd_[N][N], xx_[C + 1][C + 1], dd1[C + 1], dd2[C + 1], ee[C + 1];
int hh_[C + 1][C + 1], pp[C + 1];
int g, g_, g1, g2, h, h_, i, j, k, u, v;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
ww_[i][j] = INF;
for (h = 0; h < m; h++) {
u = uu[h], v = vv[h];
ww_[u][v] = ww[h];
}
for (g = 0; g < c; g++) {
h = hh[g], u = uu[h], v = vv[h];
ww_[u][v] = INF;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = i == j ? 0 : ww_[i][j];
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
for (g1 = 0; g1 <= c; g1++)
for (g2 = 0; g2 <= c; g2++)
xx_[g1][g2] = -INF, hh_[g1][g2] = -1;
for (h = 0; h < q; h++) {
i = ss[h], j = tt[h];
for (g = 0; g < c; g++) {
h_ = hh[g], u = uu[h_], v = vv[h_];
dd1[g] = min(dd_[i][u] + dd_[v][j], INF), dd2[g] = min(dd1[g] + ww[h_], INF);
}
dd1[c] = dd2[c] = dd_[i][j];
g_ = -1;
for (g = 0; g <= c; g++)
if (g_ == -1 || dd2[g_] > dd2[g])
g_ = g;
for (g = 0; g <= c; g++)
if (dd2[g] > dd2[g_]) {
long long x = dd1[g_] - dd1[g] + 1;
if (xx_[g_][g] < x)
xx_[g_][g] = x, hh_[g_][g] = h;
}
}
for (g = 0; g <= c; g++)
ee[g] = 0, pp[g] = -1;
while (1) {
int updated;
long long e;
updated = 0;
for (g1 = 0; g1 <= c; g1++)
for (g2 = 0; g2 <= c; g2++)
if (ee[g2] < (e = ee[g1] + xx_[g1][g2]))
ee[g2] = e, pp[g2] = g1, updated = 1;
if (!updated)
break;
}
for (g = 0; g < c; g++) {
int p = pp[g], f = p == -1 ? -1 : hh_[p][g], t;
if (p == -1)
p = c + 1;
if (f == -1)
f = q;
for (t = 0; t < 3; t++)
Tap(p >> t & 1);
for (t = 0; t < 6; t++)
Tap(f >> t & 1);
}
}
#include "Brunolib.h"
#define N 300
#define Q 60
#define C 5
#define INF 0x3f3f3f3f3f3f3f3fLL
static long long min(long long a, long long b) { return a < b ? a : b; }
static long long weight(long long xx[][C + 1][C + 1], int *pp, int *ff, int g) {
return pp[g] == -1 ? 0 : weight(xx, pp, ff, pp[g]) - (ff[g] == -1 ? INF : xx[ff[g]][pp[g]][g]);
}
static void print(long long dd[][N], long long ww[][N], int hh[][N], int n, int i, int j) {
int k;
if (i == j)
return;
for (k = 0; k < n; k++)
if (dd[i][k] + ww[k][j] == dd[i][j]) {
print(dd, ww, hh, n, i, k), Answer(hh[k][j]);
return;
}
}
void Bruno(int n, int m, int *uu, int *vv, long long *ww, int q, int *ss, int *tt, int c, int *hh, int len, int *buf) {
long long ww_[N][N], dd_[N][N], xx_[Q][C + 1][C + 1], dd1[C + 1], ee[C + 1];
int hh_[N][N], pp[C + 1], ff[C + 1];
int g, g1, g2, h, h_, i, j, k, u, v;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
ww_[i][j] = INF;
for (h = 0; h < m; h++) {
u = uu[h], v = vv[h];
ww_[u][v] = ww[h], hh_[u][v] = h;
}
for (g = 0; g < c; g++) {
h = hh[g], u = uu[h], v = vv[h];
ww_[u][v] = INF;
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = i == j ? 0 : ww_[i][j];
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
for (h = 0; h < q; h++) {
i = ss[h], j = tt[h];
for (g = 0; g < c; g++) {
h_ = hh[g], u = uu[h_], v = vv[h_];
dd1[g] = min(dd_[i][u] + dd_[v][j], INF);
}
dd1[c] = dd_[i][j];
for (g1 = 0; g1 < c; g1++)
for (g2 = 0; g2 < c; g2++)
xx_[h][g1][g2] = dd1[g1] - dd1[g2] + 1;
}
pp[c] = -1, ff[c] = -1;
for (g = 0; g < c; g++) {
int t;
pp[g] = 0;
for (t = 0; t < 3; t++)
if (buf[g * 9 + t])
pp[g] |= 1 << t;
ff[g] = 0;
for (t = 0; t < 6; t++)
if (buf[g * 9 + 3 + t])
ff[g] |= 1 << t;
if (pp[g] == c + 1)
pp[g] = -1;
if (ff[g] == q)
ff[g] = -1;
}
for (g = 0; g < c; g++)
ee[g] = weight(xx_, pp, ff, g);
for (g = 0; g < c; g++) {
h = hh[g], u = uu[h], v = vv[h];
ww_[u][v] = ee[g];
}
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = i == j ? 0 : ww_[i][j];
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
for (h = 0; h < q; h++) {
i = ss[h], j = tt[h];
print(dd_, ww_, hh_, n, i, j), Answer(-1);
}
}
