// Camping template
// Optional, but helps you to not accidently share data by using namespaces
#include "Annalib.h"
#include <iostream>
#include <vector>
#include <cassert>
#define MAXN 305
#define LL long long
#define INF ((LL) 4e18 + 5e17)
using namespace std;
namespace AnnaCode {
// Put all global variables or functions for Anna here
LL dist[MAXN][MAXN];
void Anna(int N,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[]) {
// Put your code here
for (int i=0; i<N; i++) {
for (int j=0; j < N; j++) {
dist[i][j] = i == j ? 0 : INF;
}
}
for (int i=0; i<M; i++) {
dist[A[i]][B[i]] = C[i];
}
for (int k=0; k<N; k++) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
//cout << "Check dist" << dist[0][1] << endl;
int Type[1005]={};
for (int q=0; q < Q; q++) {
for (int i=0; i<K; i++) {
if (dist[S[q]][T[q]] == dist[S[q]][A[U[i]]] + dist[B[U[i]]][T[q]] + C[U[i]]) {
Type[q] = i+1;
break;
}
}
//printf("Status of %d = %d\n",q,Type[q]);
}
for (int i=0; i<60; i+=5) {
//sends 156 bits regardless
int res = 0, exp=1;
for (int j=i; j<i+5; j++) {
res += Type[j] * exp;
exp = exp*6;
}
for (int b=1; b < 8192; b*=2) {
if (res & b) {Tap(1);}
else {Tap(0);}
}
}
}
}
void Anna(int N,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[]) {
AnnaCode::Anna(N, M, A, B, C, Q, S, T, K, U);
}
// Camping template
// Optional, but helps you to not accidently share data by using namespaces
#include "Brunolib.h"
#include <iostream>
#include <vector>
#include <cassert>
#define MAXN 305
#define LL long long
#define INF ((LL) 4e18 + 5e17)
using namespace std;
namespace BrunoCode {
// Put all global variables or functions for Bruno here
LL dist[MAXN][MAXN];
int adj[MAXN][MAXN], N;
void gen(int s, int t) {
while (s != t) {
bool good = false;
for (int i=0; i<N; i++) {
if (adj[s][i] != -1 && dist[s][i] + dist[i][t] == dist[s][t]) {
Answer(adj[s][i]);
s = i;
good = true;
break;
}
}
// assert(good);
}
}
void Bruno(int n,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[],int L,int X[]) {
// Put your code here
N=n;
for (int i=0; i<N; i++) {
for (int j=0; j < N; j++) {
dist[i][j] = i == j ? 0 : INF;
adj[i][j] = -1;
}
}
for (int i=0; i<M; i++) {
dist[A[i]][B[i]] = C[i];
if (C[i] != -1) {adj[A[i]][B[i]] = i;}
if (C[i] == -1) {dist[A[i]][B[i]]= INF;}
}
for (int k=0; k<N; k++) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
//assert(L == 156);
int Status[1000];
//decode
int cur = 0;
for (int i=0; i<156; i+=13) {
int res = 0;
for (int j=i; j < i+13; j++) {
res += (1<<(j-i)) * X[j];
}
for (int j=0; j<5; j++) {
Status[cur] = res % 6;
res /= 6, cur++;
}
}
for (int q=0; q < Q; q++) {
//printf("Read Status of %d = %d\n",q, Status[q]);
if (Status[q] == 0) {
gen(S[q], T[q]);
} else {
int a = A[U[Status[q]-1]], b = B[U[Status[q]-1]];
gen(S[q], a);
Answer(U[Status[q]-1]);
gen(b, T[q]);
}
Answer(-1);
}
}
}
void Bruno(int N,int M,int A[],int B[],long long C[],int Q,int S[],int T[],int K,int U[],int L,int X[]) {
BrunoCode::Bruno(N, M, A, B, C, Q, S, T, K, U, L, X);
}
