//chockolateman
#include<bits/stdc++.h>
#include "Aoi.h"
using namespace std;
namespace {
const long long INF = 1e15;
int n;
pair<pair<int,int>,long long> edges[20005];
long long dist[10005],par[10005];
bool visited[10005];
bool marked[20005];
vector<int> adj[10005]; //at adj store the indx of the edge
void Dijkstra()
{
for(int i = 1 ; i <= n ; i++)
{
dist[i] = INF;
visited[i] = false;
par[i] = -1;
}
dist[1] = 0;
priority_queue<pair<long long,int>> q;
q.push({0,1});
while(!q.empty())
{
int v = q.top().second;
q.pop();
if(visited[v])
continue;
visited[v] = true;
for(auto e : adj[v])
{
int u = edges[e].first.first;
if(u==v)
u = edges[e].first.second;
long long w = edges[e].second;
if(dist[v] + w < dist[u])
{
dist[u] = dist[v] + w;
par[u] = e; //keep the edge of your par
q.push({-dist[u],u});
}
}
}
}
void mark_path(int v)
{
if(v==1)
return;
int e = par[v];
marked[e] = true;
int p = edges[e].first.first;
if(p==v)
p = edges[e].first.second;
mark_path(p);
}
}
std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)
{
n = N;
for(int i = 0 ; i < M ; i++)
{
A[i]++;
B[i]++;
edges[i] = {{A[i],B[i]},C[i]};
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
Dijkstra();
string s;
for(int i = 0 ; i < Q ; i++)
{
T[i]++;
for(int j = 0 ; j < M ; j++)
marked[j] = false;
mark_path(T[i]);
for(int j = 0 ; j < K ; j++)
if(marked[X[j]])
s.push_back('1'); //means that edges is usefull
else
s.push_back('0');
}
return s;
}
//chockolateman
#include<bits/stdc++.h>
#include "Bitaro.h"
using namespace std;
namespace {
const long long nINF = 1e15;
int nn;
pair<pair<int,int>,long long> nedges[20005];
long long ndist[10005],npar[10005];
bool nvisited[10005];
bool nmarked[20005];
vector<int> nadj[10005]; //at adj store the indx of the edge
vector<int> path;
void nDijkstra()
{
for(int i = 1 ; i <= nn ; i++)
{
ndist[i] = nINF;
nvisited[i] = false;
npar[i] = -1;
}
ndist[1] = 0;
priority_queue<pair<long long,int>> q;
q.push({0,1});
while(!q.empty())
{
int v = q.top().second;
q.pop();
if(nvisited[v])
continue;
nvisited[v] = true;
for(auto e : nadj[v])
{
int u = nedges[e].first.first;
if(u==v)
u = nedges[e].first.second;
long long w = nedges[e].second;
if(ndist[v] + w < ndist[u])
{
ndist[u] = ndist[v] + w;
npar[u] = e; //keep the edge of your par
q.push({-ndist[u],u});
}
}
}
}
void get_path(int v)
{
if(v==1)
return;
int e = npar[v];
int p = nedges[e].first.first;
if(p==v)
p = nedges[e].first.second;
get_path(p);
path.push_back(e);
}
} // namespace
void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X,std::string s)
{
nn = N;
for(int i = 0 ; i < M ; i++)
{
A[i]++;
B[i]++;
nedges[i] = {{A[i],B[i]},C[i]};
nadj[A[i]].push_back(i);
nadj[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')
nedges[X[j]].second = 0;
else
nedges[X[j]].second = nINF;
nDijkstra();
path.clear();
T[i]++;
get_path(T[i]);
answer(path);
}
}
