#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
typedef long long ll;
const ll INF = 1e18;
int n;
vector<int> A, B;
vector<ll> C;
vector<int> con[10005];
vector<ll> dist[10005];
vector<int> prec[10005];
void calc_dist(int src)
{
dist[src].resize(n, INF);
prec[src].resize(n, -1);
priority_queue<pair<int,int>> pq;
dist[src][src] = 0;
pq.push({0, src});
while(!pq.empty())
{
int nod = pq.top().second;
int cdist = -pq.top().first;
pq.pop();
if(cdist != dist[src][nod])
continue;
for(auto eid:con[nod])
{
int adj = A[eid] + B[eid] - nod;
ll w = C[eid];
if(dist[src][adj] > dist[src][nod] + w)
{
dist[src][adj] = dist[src][nod] + w;
prec[src][adj] = eid;
pq.push({-dist[src][adj], adj});
}
}
}
}
}
std::string aoi(int N, int M, int Q, int K, std::vector<int> copA,
std::vector<int> copB, std::vector<ll> copC,
std::vector<int> T, std::vector<int> X)
{
//sort(X.begin(), X.end());
assert(n == 0);
n = N;
A = copA;
B = copB;
C = copC;
for(int i=0;i<M;i++)
{
con[A[i]].push_back(i);
con[B[i]].push_back(i);
}
calc_dist(0);
/*for(int i=0;i<K;i++)
{
calc_dist(A[X[i]]);
calc_dist(B[X[i]]);
}*/
for(int i=0;i<Q;i++)
{
calc_dist(T[i]);
}
string sol;
for(int i=0;i<Q;i++)
{
for(int j=0;j<K;j++)
{
if(dist[0][A[X[j]]] + dist[T[i]][B[X[j]]] + C[X[j]] == dist[0][T[i]] || dist[0][B[X[j]]] + dist[T[i]][A[X[j]]] + C[X[j]] == dist[0][T[i]])
{
sol.push_back('1');
}
else
{
sol.push_back('0');
}
}
}
return sol;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
typedef long long ll;
const ll INF = 1e18;
int n;
vector<int> A, B;
vector<ll> C;
vector<int> con[10005];
vector<ll> dist[10005];
vector<int> prec[10005];
void calc_dist(int src)
{
dist[src].resize(n, INF);
prec[src].resize(n, -1);
priority_queue<pair<int,int>> pq;
dist[src][src] = 0;
pq.push({0, src});
while(!pq.empty())
{
int nod = pq.top().second;
int cdist = -pq.top().first;
pq.pop();
if(cdist != dist[src][nod])
continue;
for(auto eid:con[nod])
{
int adj = A[eid] + B[eid] - nod;
ll w = C[eid];
if(dist[src][adj] > dist[src][nod] + w)
{
dist[src][adj] = dist[src][nod] + w;
prec[src][adj] = eid;
pq.push({-dist[src][adj], adj});
}
}
}
}
}
void bitaro(int N, int M, int Q, int K, std::vector<int> copA, std::vector<int> copB,
std::vector<long long> copC, std::vector<int> T, std::vector<int> X,
std::string s)
{
//sort(X.begin(), X.end());
n = N;
A = copA;
B = copB;
C = copC;
for(int i=0;i<M;i++)
{
con[A[i]].push_back(i);
con[B[i]].push_back(i);
}
for(int i=0;i<Q;i++)
{
for(int j=0;j<K;j++)
{
if(s[i*K + j] == '1')
{
C[X[j]] = 0;
}
else
{
C[X[j]] = INF;
}
}
calc_dist(0);
vector<int> sol;
int cur = T[i];
while(cur != 0)
{
int eid = prec[0][cur];
sol.push_back(eid);
cur = A[eid] + B[eid] - cur;
}
answer(sol);
}
}
/*
3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1
*/
