#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // namespace
string aoi(int n, int m, int q, int k, vector<int> A,
vector<int> B, vector<long long> C,
vector<int> T, vector<int> X) {
vector<array<int,2>>g[n];
for(int i = 0;i<m;i++){
g[A[i]].push_back({B[i],i});
g[B[i]].push_back({A[i],i});
}
int rev[m];
fill(rev,rev+m,-1);
for(int i = 0;i<k;i++){
rev[X[i]]=i;
}
priority_queue<array<long long,2>,vector<array<long long,2>>,greater<array<long long,2>>>pq;
int dist[n];
fill(dist,dist+n,-1);
dist[0]=0;
for(array<int,2> e : g[0]){
pq.push({C[e[1]],e[1]});
}
int p[n];
fill(p,p+n,-1);
p[0]=-2;
while(!pq.empty()){
array<long long,2>e = pq.top();
pq.pop();
int node = A[e[1]];
if(p[node]!=-1){
node=B[e[1]];
}
if(p[node]!=-1){
continue;
}
p[node]=e[1];
dist[node]=e[0];
for(array<int,2>ed : g[node]){
pq.push({dist[node]+C[ed[1]],ed[1]});
}
}
string s = "";
for(int i = 0;i<q*k;i++){
s+="0";
}
for(int i = 0;i<q;i++){
int cur = T[i];
while(cur){
int edge = p[cur];
if(rev[edge]!=-1){
s[i*k+rev[edge]]='1';
}
if(cur==A[edge]){
cur=B[edge];
}
else{
cur=A[edge];
}
}
}
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // namespace
void bitaro(int n, int m, int q, int k, vector<int> A, vector<int> B,
vector<long long> C, vector<int> T, vector<int> X,
string s) {
for(int i : X){
C[i]=-1;
}
vector<array<int,2>>g[n];
for(int i = 0;i<m;i++){
g[A[i]].push_back({B[i],i});
g[B[i]].push_back({A[i],i});
}
int rev[m];
fill(rev,rev+m,-1);
for(int i = 0;i<k;i++){
rev[X[i]]=i;
}
for(int i = 0;i<q;i++){
priority_queue<array<long long,2>,vector<array<long long,2>>,greater<array<long long,2>>>pq;
int dist[n];
fill(dist,dist+n,-1);
dist[0]=0;
for(array<int,2> e : g[0]){
pq.push({C[e[1]],e[1]});
}
int p[n];
fill(p,p+n,-1);
p[0]=-2;
while(!pq.empty()){
array<long long,2>e = pq.top();
pq.pop();
int node = A[e[1]];
if(p[node]!=-1){
node=B[e[1]];
}
if(p[node]!=-1){
continue;
}
p[node]=e[1];
dist[node]=e[0];
for(array<int,2>ed : g[node]){
if(C[ed[1]]==-1){
if(s[i*k+ed[1]]=='1'){
pq.push({dist[node]+0,ed[1]});
}
}
else{
pq.push({dist[node]+C[ed[1]],ed[1]});
}
}
}
int cur = T[i];
vector<int>v;
while(cur){
int edge = p[cur];
v.push_back(edge);
if(cur==A[edge]){
cur=B[edge];
}
else{
cur=A[edge];
}
}
reverse(v.begin(),v.end());
answer(v);
}
}
