#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <utility>
#include <time.h>
#include <unistd.h>

// ==== using ===== //
using std::cout;
using std::cerr;
using std::endl;
// ================ // 


// ===== class ====== //

class nodeClass
{
  public:
    nodeClass(){ preIdx = -1; nextIdx = -1; }
    int index;
    bool done;
    double cost;

    //nodeClass *pre;
    //nodeClass *next;

    int preIdx;
    int nextIdx;
    std::vector<nodeClass> optRouteInfo;

    int getIndex(){return index; }
    int getIndexForOut(){ return index + 1; }
    std::vector<int>* routeTo(int i);

    std::map<int, std::vector<int> > routeToMap;

};


class edgeClass
{
  public:
    edgeClass(){ from = NULL; to = NULL; }
    double dist;
    nodeClass *from;
    nodeClass *to;

};

class orderClass
{
  public:
    bool done;
    int id;
    int ordertime;
    int waitingtime;
    nodeClass *customer;

    double dScore(double dt1, double dt2);
};


// ================= //

// ==== global ======= //
clock_t start, end;
int V, E, Tmax, nowTime;
std::map<int, std::map<int, edgeClass> > edgeMap;
std::vector<std::vector<edgeClass> > edges;
std::map<int, nodeClass> nodeMap;
std::vector<nodeClass> nodes;
std::vector<std::vector<orderClass> > orders;
std::vector<int> ansBestRoute;
std::vector<int> ansBestRoute2;
// ==================== //


// ===== function ====== //

int Import();
int Export();
int Opt();
int GatherOrder(std::vector<orderClass> &orders, std::vector<orderClass> &notDelivOrders, int t1, int t2);
int SearchRoute(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, double &score, std::vector<int> &aRouteEdge);
int createFeasibleRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute);
int createRoute(std::vector<int> &pathNodes, std::vector<int> &aRoute);
int Dikstra(int fromIdx, int toIdx);

double GetRouteDist(std::vector<int> &aRoute);
double GetScoreRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute);
double GetScoreRoute2(std::vector<int> &aRoute);
double GetScoreRoute3(std::vector<int> &aRoute, std::vector<int> &nonNodes);
void displayRoute(std::vector<int> &aRoute);
void outputRoute(std::vector<int> &aRoute);

double GetDist(int i, int j)
{
  if(i == j)
  { return 0; }

  std::map<int, edgeClass> *tmpMap = &edgeMap[i];

  if(tmpMap->find(j) == tmpMap->end())
  { return 1e+16; }
  else 
  { return tmpMap->at(j).dist; }
}
// ==================== //

int main() 
{

  int error = 0;

  srand((unsigned int) time(NULL));
  start = clock();

  error = Import();
  error = Opt();
  error = Export();

  cerr << "done[opt] " << endl;

  return 0;
}

int Import()
{
  int error = 0;
  std::vector<std::vector<std::pair<int, int> > > G(V);

  // recieve |V| and |E|
  std::cin >> V >> E;

  // create nodes
  for(int i = 0; i < V; ++i)
  { 
    nodeClass aNode;
    aNode.index = i;
    aNode.done = false;

    nodes.push_back(aNode);
    nodeMap[i] = aNode;
  }

  for(int i = 0; i < V; ++i)
  { edges.push_back(std::vector<edgeClass>()); }

  for(int i = 0; i < E; i++) 
  {
    // recieve edges
    int u, v, d; std::cin >> u >> v >> d;
    u--; v--;
    //G[u].push_back({v, d});
    //G[v].push_back({u, d});

    edgeClass aEdge1, aEdge2;
    aEdge1.from = &nodeMap[u];
    aEdge1.to = &nodeMap[v];
    aEdge1.dist = d;

    aEdge2.from = &nodeMap[v];
    aEdge2.to = &nodeMap[u];
    aEdge2.dist = d;

    edgeMap[u][v] = aEdge1;
    edgeMap[v][u] = aEdge2;

    edges[u].push_back(aEdge1);
    edges[v].push_back(aEdge2);
  }

  std::cin >> Tmax;

  // recieve order info
  int nOrder = 0;
  for(int i = 0; i < Tmax; i++) 
  {
    int Nnew; std::cin >> Nnew;
    std::vector<orderClass> tmpvec;

    for(int j = 0; j < Nnew; j++)
    {
      int new_id, dst; 
      std::cin >> new_id >> dst;
      --dst;

      orderClass aOrder;
      aOrder.id = new_id;
      aOrder.ordertime = i;
      aOrder.customer = &nodeMap[dst];

      tmpvec.push_back(aOrder);
      ++nOrder;
    }

    orders.push_back(tmpvec);
  }

  cerr << "done Data Import... {V, E, O} = {" << V << ", " << E << ", " << nOrder << "} " << endl;
  return error;
}

int Export()
{
  int error = 0;

  outputRoute(ansBestRoute);

  return error;

}

int Opt()
{

  int error = 0;
  try
  {
    int nOrder = 0;
    int lastTime = 0;
    bool fin = false;
    double score_tot = 0.0;
    double maxVal = 0.0;

    //最短経路チェック
    for(int i = 0; i < nodes.size(); ++i)
    { Dikstra(i, -1); }
    //

    std::vector<orderClass> stackedOrders, notDelivOrders;
    std::vector<int> routeNodes, routeEdges;
    std::map<double, std::vector<int> > routeNodesMap;
    std::vector<std::vector<int> > routeNodesVec;
    std::vector<std::vector<int> > noNodesVec;

    const int N = 1;

    for(int i = 0; i < N; ++i)
    {
      nowTime = 0;
      score_tot = 0.0;
      routeNodes.clear(); routeEdges.clear();

      routeNodes.push_back(0);

      while(!fin)
      {
	//decide waiting time
	int waitingTime_startpoint = 0;
	nowTime += waitingTime_startpoint;

	//gather orders
	stackedOrders.clear();
	error = GatherOrder(stackedOrders, notDelivOrders, lastTime, nowTime);

	if(error == 1 && nowTime >= Tmax)
	{ break; }

	lastTime = nowTime + 1;

	if(stackedOrders.size() == 0)
	{ 
	  nowTime += 1; 
	  routeNodes.push_back(0); 
	  routeEdges.push_back(0);
	  continue; 
	}

	double score = 0;
	std::vector<int> aRouteEdge;
	aRouteEdge.reserve(10000);
	error = SearchRoute(stackedOrders, notDelivOrders, score, aRouteEdge);

	std::map<int, int> notDelivMap;
	for(int i = 0; i < notDelivOrders.size(); ++i)
	{ notDelivMap[notDelivOrders[i].id] = 1; }

	for(int i = 0; i < stackedOrders.size(); ++i)
	{
	  if(notDelivMap.find(stackedOrders[i].id) != notDelivMap.end())
	  { continue; }
	  routeNodes.push_back(stackedOrders[i].customer->index);
	}
	routeNodes.push_back(0);

	for(int i = 0; i < aRouteEdge.size() - 1; ++i)
	{ routeEdges.push_back(aRouteEdge[i]); }

	score_tot += score;

      }

      std::vector<int> nNodes;
      //double score = GetScoreRoute2(routeEdges);
      
      double score = GetScoreRoute3(routeEdges, nNodes);
      routeNodesMap[-score] = routeNodes;
      routeNodesVec.push_back(routeNodes);
      noNodesVec.push_back(nNodes);
      cerr << "TIME " << nowTime << endl;
      cerr << "score = " << score << endl;

    }

    ansBestRoute = routeEdges;
    ansBestRoute2 = routeEdges;

    std::vector<int> tmpRoute;
    std::vector<int> bestRouteNodes = routeNodes;

    for(int loop = 0; loop < 100000; ++loop)
    {
      
	int kk = rand() % routeNodesVec.size();

	auto nold = routeNodesVec[kk];
	auto nold2 = noNodesVec[kk];

	int ii = rand() % routeNodesVec[kk].size();
	int jj = rand() % routeNodesVec[kk].size();

  	if(ii == 0 || jj == 0)
	{ continue; }
	  
	int dummy = routeNodesVec[kk][jj];
	routeNodesVec[kk][jj] = routeNodesVec[kk][ii];
	routeNodesVec[kk][ii] = dummy;


	double rnd = (double) rand() / RAND_MAX;

	if(rnd < 0.9)
	{ 
	    int m = rand() % routeNodesVec[kk].size();
	    //if(m > 0 )
	    {
		//int l = rand() % nodes.size();
		//int l = rand() % noNodesVec[kk].size();
		//l = noNodesVec[kk][l];
		//routeNodesVec[kk][m] = l;
		for(int l = 0; l < noNodesVec[kk].size(); ++l)
		{
		    rnd = (double) rand() / RAND_MAX;
		    int m = rand() % routeNodesVec[kk].size();
		    if(m > 0 && rnd < 0.2) 
		    {
		    routeNodesVec[kk].insert(routeNodesVec[kk].begin() + m, noNodesVec[kk][l]);
		    }
		}
	    }
	    
	}


	std::vector<int> tmpRoute, noNode;
	error = createRoute(routeNodesVec[kk], tmpRoute);
	//double scoreA_test = GetScoreRoute2(tmpRoute);
	double scoreA_test = GetScoreRoute3(tmpRoute, noNode);

	if(scoreA_test > maxVal )
	{ ansBestRoute = tmpRoute; maxVal = scoreA_test; noNodesVec[kk] = noNode;}

	else 
	{  routeNodesVec[kk] = nold; noNodesVec[kk] = nold2;}

#if 0
      int ii = rand() % routeNodesMap.size();
      int jj = rand() % routeNodesMap.size();

      if(ii == 0 || jj == 0)
      { continue; }

      std::vector<int> A, B;
      int n = 0;
      for(auto itr = routeNodesMap.begin(); itr != routeNodesMap.end(); ++itr, ++n)
      {
	if(ii == n)
	{ A = itr->second; }
	if(jj == n)
	{ B = itr->second; }
      }

      int kk = rand() % ( A.size() < B.size() ? A.size() : B.size());

      std::vector<int> child_A, child_B;
      child_A.reserve(10000);
      child_B.reserve(10000);

      for(int i = 0; i < kk; ++i)
      { child_A.push_back(A[i]); }
      for(int i = kk; i < B.size(); ++i)
      { child_A.push_back(B[i]); }	

      for(int i = 0; i < kk; ++i)
      { child_B.push_back(B[i]); }
      for(int i = kk; i < A.size(); ++i)
      { child_B.push_back(A[i]); }

      double rnd = (double) rand() / RAND_MAX;
      if(rnd < 0.2)
      { 
	int ll = rand() % child_A.size();
	if(ll > 0)
	{
	  int pp = rand() % nodes.size();
	  child_A[ll] = pp; 
	}
      }
      rnd = (double) rand() / RAND_MAX;
      if(rnd < 0.2)
      { 
	int ll = rand() % child_B.size();
	if(ll > 0)
	{
	  int pp = rand() % nodes.size();
	  child_B[ll] = pp; 
	}
      }

      std::vector<int> route_A, route_B;
      error = createRoute(child_A, route_A);
      error = createRoute(child_B, route_B);

      double scoreA, scoreB;

      scoreA = GetScoreRoute2(route_A); 
      scoreB = GetScoreRoute2(route_B);

      for(int p = 0; p < 0; ++p)
      {
	auto oldA = child_A, oldB = child_B;

	int ii_A = rand() % child_A.size(), jj_A = rand() % child_A.size();
	int ii_B = rand() % child_B.size(), jj_B = rand() % child_B.size();

	if(ii_A != 0 && jj_A != 0)
	{
	  int dummy = child_A[jj_A];
	  child_A[jj_A] = child_A[ii_A];
	  child_A[ii_A] = dummy;

	  if(0 < ii_A && ii_A < child_A.size())
	  { 
	    if(child_A[ii_A] == child_A[ii_A - 1] && child_A[ii_A] != 0)
	    { child_A.erase(child_A.begin() + ii_A); }
	    if(child_A[ii_A] == child_A[ii_A + 1] && child_A[ii_A] != 0)
	    { child_A.erase(child_A.begin() + ii_A); }
	  }
	  if(0 < jj_A && jj_A < child_A.size())
	  { 
	    if(child_A[jj_A] == child_A[jj_A - 1] && child_A[jj_A] != 0)
	    { child_A.erase(child_A.begin() + jj_A); }
	    if(child_A[jj_A] == child_A[jj_A + 1] && child_A[jj_A] != 0)
	    { child_A.erase(child_A.begin() + jj_A); }
	  }

	  std::vector<int> tmpRoute;
	  error = createRoute(child_A, tmpRoute);
	  double scoreA_test = GetScoreRoute2(tmpRoute);

	  if(scoreA_test < scoreA)
	  { child_A = oldA; }
	  else 
	  { scoreA = scoreA_test; }
	}

	if(ii_B != 0 && jj_B != 0)
	{
	  int dummy = child_B[jj_B];
	  child_B[jj_B] = child_B[ii_B];
	  child_B[ii_B] = dummy;

	  if(0 < ii_B && ii_B < child_B.size())
	  { 
	    if(child_B[ii_B] == child_B[ii_B - 1] && child_B[ii_B] != 0)
	    { child_B.erase(child_B.begin() + ii_B); }
	    if(child_B[ii_B] == child_B[ii_B + 1] && child_B[ii_B] != 0)
	    { child_B.erase(child_B.begin() + ii_B); }
	  }
	  if(0 < jj_B && jj_B < child_B.size())
	  { 
	    if(child_B[jj_B] == child_B[jj_B - 1] && child_B[jj_B] != 0)
	    { child_B.erase(child_B.begin() + jj_B); }
	    if(child_B[jj_B] == child_B[jj_B + 1] && child_B[jj_B] != 0)
	    { child_B.erase(child_B.begin() + jj_B); }
	  }

	  std::vector<int> tmpRoute;
	  error = createRoute(child_B, tmpRoute);
	  double scoreB_test = GetScoreRoute2(tmpRoute);

	  if(scoreB_test < scoreB)
	  { child_B = oldB; }
	  else 
	  { scoreB = scoreB_test; }
	}
      }
      routeNodesMap[-scoreA] = child_A;
      routeNodesMap[-scoreB] = child_B;

      if(scoreA > maxVal) { maxVal = scoreA; }
      if(scoreB > maxVal) { maxVal = scoreB; }

      std::map<double, std::vector<int> > tmpMap;
      n = 0;
      for(auto itr = routeNodesMap.begin(); itr != routeNodesMap.end(); ++itr, ++n)
      { 
	if(n == N) break;
	tmpMap[itr->first] = itr->second;
      }

      routeNodesMap = tmpMap;
#endif
      end = clock();
      double time = static_cast<double>((end - start) / CLOCKS_PER_SEC);
      if(time > 28.5)
      { break; }

      cerr << "best score is " << maxVal << ", " << time << endl;

    }

    //ansBestRoute.clear();
    //error = createRoute(routeNodesMap.begin()->second, ansBestRoute);	
    //cerr << routeNodesMap.begin()->first << endl;
  }
  catch(std::exception e)
  {

  }

  return error;

}

int GatherOrder(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, int t1, int t2)
{
  int error = 0;
  const int nOrderSize = orders.size();

  for(int i = 0; i < notDelivOrders.size(); ++i)
  { sOrders.push_back(notDelivOrders[i]); }
  notDelivOrders.clear();

  //gather orders t1~t2
  for(int t = t1; t <= t2; ++t)
  {
    if(t >= nOrderSize)
    { break; }
    std::vector<orderClass> *tmpVec = &orders[t];

    for(int i = 0; i < tmpVec->size(); ++i)
    { sOrders.push_back(tmpVec->at(i)); }
  }
  //end gather

  if(sOrders.size() == 0)
  { error = 1; }
  return error;

}


int createFeasibleRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute)
{

  int error = 0;
  int thisNode = 0;
  const int nShuffle = 100;

  std::map<int, int> tmpMap;

  for(int i = 0; i < sOrders.size(); ++i)
  { tmpMap[sOrders[i].customer->index] = 0; }
  for(int i = 0; i < sOrders.size(); ++i)
  { tmpMap[sOrders[i].customer->index] += 1; }

  for(int i = 0; i < nShuffle; ++i)
  { 
    int ii = rand() % sOrders.size();
    int jj = rand() % sOrders.size();

    auto dummy = sOrders[jj];
    sOrders[jj] = sOrders[ii];
    sOrders[ii] = dummy;
  }

  bool fin = false;
  int iloop = 0;
  std::map<int, int> pathedMap;

  nodeClass *sNode = NULL, *eNode = NULL;
  sNode = &nodes[0];

  while(1)
  {
    if(iloop < sOrders.size())
    { 
      eNode = &nodes[sOrders[iloop].customer->index]; 

      if(pathedMap.find(eNode->index) != pathedMap.end())
      { ++iloop; continue; }
    }
    else 
    { eNode = &nodes[0]; fin = true; }

    std::vector<int> *route = sNode->routeTo(eNode->index);

    for(int i = 0; i < route->size(); ++i)
    { 
      if(aRoute.size() > 0 && i == 0)
      { continue; }
      if(route->at(i) == 0 && aRoute.size() > 0)
      { fin = true; aRoute.push_back(route->at(i)); break;}
      aRoute.push_back(route->at(i)); 
    }
    for(int i = 0; i < route->size(); ++i)
    { pathedMap[route->at(i)] = 1; }

    if(fin) 
    { break; }
    sNode = eNode;
    ++iloop;
  }
  //end search route

  return error;
}

int SearchRoute(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, double &score, std::vector<int> &aRouteEdge)
{
  int error = 0;
  int nRoute = 10;
  std::vector<std::vector<int> > routeList;
  std::map<int, std::vector<std::vector<int> > > sortedRouteMap;
  std::vector<int> bestRoute;

  double maxval = -1.0e+16;
  double minval = 1.0e+16;
  double dist = 0.0;
  int iRoute = -1;

  //ランダムに経路作成
  for(int i = 0; i < nRoute; ++i)
  {
    std::vector<int> aRoute;
    error = createFeasibleRoute(sOrders, aRoute);
    routeList.push_back(aRoute);
  }

  for(int i = 0; i < routeList.size(); ++i)
  { 
    double score = GetScoreRoute(sOrders, routeList[i]);
    double tmpdist = GetRouteDist(routeList[i]);
    if(score > maxval && tmpdist < 1e6)
    { 
      iRoute = i;
      maxval = score;
      dist = tmpdist; 
      minval = dist;
      bestRoute = routeList[i];
    }
  }

  std::map<int, std::vector<int> > orderIdxMap;

  for(int i = 0; i < sOrders.size(); ++i)
  { 
    int idx = sOrders[i].customer->index;
    orderIdxMap[idx].push_back(i);
  }

  for(int i = 0; i < bestRoute.size(); ++i)
  {
    int idx = bestRoute[i]; 
    if(orderIdxMap.find(idx) == orderIdxMap.end())
    { continue; }
    //orderIdxMap[idx] = -1;
    std::vector<int> tmpvec = orderIdxMap[idx];
    for(int j = 0; j < tmpvec.size(); ++j)
    { orderIdxMap[idx][j] = -1; }
  }

  for(auto itr = orderIdxMap.begin(); itr != orderIdxMap.end(); ++itr)
  {
    std::vector<int> *tmpvec = &itr->second;

    for(int j = 0; j < tmpvec->size(); ++j)
    {
      int idx = tmpvec->at(j);
      if(idx == -1)
      { continue; }
      notDelivOrders.push_back(sOrders[idx]);
    }
  }

  aRouteEdge = bestRoute;
  nowTime += dist;
  score = maxval;

  return error;
}

double GetRouteDist(std::vector<int> &aRoute)
{
  double dist_tot = 0;
  for(int i  = 0; i < aRoute.size() - 1; ++i)
  {
    dist_tot += GetDist(aRoute[i], aRoute[i + 1]);
  }
  return (dist_tot);
}


double GetScoreRoute3(std::vector<int> &aRoute, std::vector<int> &nonNodes)
{
  double score = 0.0; 
  int dt = 0;
  const int nOrderSize = orders.size();

  int lastStoreTime = 0;
  std::map<int, std::vector<orderClass*> > node2Orders;

  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    //arrive store
    if(aRoute[i] == 0)
    {

      for(int t = lastStoreTime ; t <= dt; ++t)
      {
	if(t >= nOrderSize)
	{ continue; }
	std::vector<orderClass> *tmpVec = &orders[t];

	for(int j = 0; j < tmpVec->size(); ++j)
	{ 
	  tmpVec->at(j).done = false;
	  node2Orders[tmpVec->at(j).customer->index].push_back(&tmpVec->at(j)); 
	}
      }	
      lastStoreTime = dt + 1;
    }

    if(node2Orders.find(aRoute[i]) != node2Orders.end())
    {


      std::vector<orderClass*> *ordervec = &node2Orders[aRoute[i]]; 
      for(int j = 0; j < ordervec->size(); ++j)
      {
	orderClass *aOrder = ordervec->at(j);

	if(aOrder->done) 
	{ continue; }

	if(dt >= Tmax)
	{ break; }

	double arrivalTime = dt, aOrderTime = aOrder->ordertime;
	double waitTime = arrivalTime - aOrderTime;

	aOrder->done = true;

	score += (Tmax * Tmax - waitTime * waitTime);
      }
      //node2Orders.erase(aRoute[i]);
    }

    dt += GetDist( aRoute[i], aRoute[i + 1] );

    if(dt >= 1e+6)
    { return 0.0; }

    if(aRoute[i] == aRoute[i + 1]) 
    { dt += 1; }

    if(dt >= Tmax)
    { break; }
  }


  for(auto itr = node2Orders.begin(); itr != node2Orders.end(); ++itr)
  {
      int index = itr->first;
      std::vector<orderClass*> vec = itr->second;

      for(int i = 0; i < vec.size(); ++i)
      {
	  if(vec[i]->done)
	  { continue; }

	  nonNodes.push_back(vec[i]->customer->index);
      }

  }

  nowTime = dt;

  return score;
}

double GetScoreRoute2(std::vector<int> &aRoute)
{
  double score = 0.0; 
  int dt = 0;
  const int nOrderSize = orders.size();

  int lastStoreTime = 0;
  std::map<int, std::vector<orderClass*> > node2Orders;

  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    //arrive store
    if(aRoute[i] == 0)
    {

      for(int t = lastStoreTime ; t <= dt; ++t)
      {
	if(t >= nOrderSize)
	{ continue; }
	std::vector<orderClass> *tmpVec = &orders[t];

	for(int j = 0; j < tmpVec->size(); ++j)
	{ 
	  tmpVec->at(j).done = false;
	  node2Orders[tmpVec->at(j).customer->index].push_back(&tmpVec->at(j)); 
	}
      }	
      lastStoreTime = dt + 1;
    }

    if(node2Orders.find(aRoute[i]) != node2Orders.end())
    {


      std::vector<orderClass*> *ordervec = &node2Orders[aRoute[i]]; 
      for(int j = 0; j < ordervec->size(); ++j)
      {
	orderClass *aOrder = ordervec->at(j);

	if(aOrder->done) 
	{ continue; }

	if(dt >= Tmax)
	{ break; }

	double arrivalTime = dt, aOrderTime = aOrder->ordertime;
	double waitTime = arrivalTime - aOrderTime;

	aOrder->done = true;

	score += (Tmax * Tmax - waitTime * waitTime);
      }
      //node2Orders.erase(aRoute[i]);
    }

    dt += GetDist( aRoute[i], aRoute[i + 1] );

    if(dt >= 1e+6)
    { return 0.0; }

    if(aRoute[i] == aRoute[i + 1]) 
    { dt += 1; }

    if(dt >= Tmax)
    { break; }
  }

  nowTime = dt;

  return score;
}

double GetScoreRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute)
{
  double score = 0, dt = nowTime;
  std::map<int, int> nodeArriaValTime;
  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    if(aRoute[i] == aRoute[i + 1])
    { dt += 1; }
    else 
    { dt += GetDist(aRoute[i], aRoute[i+1]); }
    if(nodeArriaValTime.find(aRoute[i+1]) == nodeArriaValTime.end())
    { nodeArriaValTime[aRoute[i+1]] = dt;}
  }

  int cnt = 0;
  for(int i = 0; i < sOrders.size(); ++i)
  {
    if(nodeArriaValTime.find(sOrders[i].customer->index) == nodeArriaValTime.end())
    { cnt += 1; continue; }
    double arrivalTime = nodeArriaValTime[sOrders[i].customer->index]; 
    double orderTime = sOrders[i].ordertime;	
    double waitingTime = arrivalTime - orderTime;
    score += Tmax * Tmax - waitingTime * waitingTime;
  }

//  score -= Tmax * Tmax * cnt;

  return (score);

}

int Dikstra(int fromIdx, int toIdx)
{
  for(int i = 0; i < nodes.size(); ++i)
  { 
    nodes[i].done = false;
    nodes[i].cost = -1;
    nodes[i].preIdx = nodes[i].nextIdx = -1;
  }    

  nodes[fromIdx].cost= 0;

  while(true)
  {
    nodeClass *aProcNode = NULL;

    for(int i = 0; i < nodes.size(); ++i)
    {
      nodeClass *aNode = &nodes[i];

      if(aNode->done || aNode->cost < 0)
      { continue; }

      if(aProcNode == NULL)
      { aProcNode = aNode; continue; }

      if(aNode->cost < aProcNode->cost)
      { aProcNode  = aNode; }
    }

    if(aProcNode == NULL)
    { break; }

    aProcNode->done = true;

    std::vector<edgeClass> tmpEdgeVec = edges[aProcNode->index];

    for(int i = 0; i < tmpEdgeVec.size(); ++i)
    {
      edgeClass *aEdge = &tmpEdgeVec[i];
      nodeClass *aNode = &nodes[aEdge->to->index];

      double cost = aProcNode->cost + aEdge->dist;
      bool update = (aNode->cost < 0) || (aNode->cost > cost);

      if(update)
      {
	aNode->cost = cost;
	aNode->preIdx = aProcNode->index;
	aProcNode->nextIdx = aNode->index;
      }
    }

  }

  for(int i = 0; i < nodes.size(); ++i)
  { 
    nodeClass aNode;
    aNode.index = nodes[i].index;
    aNode.done = nodes[i].done;
    aNode.preIdx = nodes[i].preIdx;
    aNode.nextIdx = nodes[i].nextIdx;
    aNode.cost = nodes[i].cost;
    //nodes[fromIdx].optRouteInfo = nodes;
    nodes[fromIdx].optRouteInfo.push_back(aNode);
  }

  if(toIdx < 0)
  { return 0; }

  nodeClass *currentNode = &nodes[toIdx];

  while(true)
  {
    nodeClass *nextNode = &nodes[currentNode->preIdx];

    if(nextNode == NULL || nextNode->index == fromIdx)
    { break; }	   
    currentNode = nextNode;

  }

  return 0;
}

std::vector<int> *nodeClass::routeTo(int toIdx)
{

  if(this->routeToMap.find(toIdx) != this->routeToMap.end())
  { return &this->routeToMap[toIdx]; }

  std::vector<int> rvec, tmpvec;
  nodeClass *currentNode = &optRouteInfo[toIdx];

  tmpvec.push_back(currentNode->index);

  while(true)
  {
    nodeClass *nextNode = &optRouteInfo[currentNode->preIdx];

    if(nextNode != NULL)
    { tmpvec.push_back(nextNode->index); }
    if(nextNode == NULL || nextNode->index == this->index)
    { break; }	   
    currentNode = nextNode;
  }

  for(int i = tmpvec.size() - 1; i >= 0; --i)
  { rvec.push_back(tmpvec[i]); }

  routeToMap[toIdx] = rvec;

  return  &routeToMap[toIdx];
}

void displayRoute(std::vector<int> &aRoute)
{

  cerr << "route => ";
  for(int i = 0; i < aRoute.size(); ++i)
  { cerr << aRoute[i] << " " ; }
  cerr << endl;

  return;
}

int createRoute(std::vector<int> &pathNodes, std::vector<int> &aRoute)
{

  int error = 0;

  double dt = 0, dt_last = 0;
  std::map<int, int> pathedMap;
  int nodeIdx_from = 0, nodeIdx_to = 0;

  std::map<int, bool> orderMap;

  for(int i = 0; i < pathNodes.size() - 1; ++i)
  {
    int k = i + 1;
    nodeIdx_from = pathNodes[i];
    nodeIdx_to = pathNodes[k];

    if(pathedMap.find(nodeIdx_to) != pathedMap.end())
    {
      int l;
      for(l = i + 2; l < pathNodes.size(); ++l)
      {
	nodeIdx_to = pathNodes[l];
	if(pathedMap.find(nodeIdx_to) == pathedMap.end())
	{ break; }
      }
      i = l - 1;
    }


    if(nodeIdx_from == 0)
    {
	for(int t = dt_last; t <= dt; ++t)
	{ 
	    if(t >= Tmax)
	    { break; }
	    std::vector<orderClass> *tmpOrders = &orders[t];

	  for(int o = 0; o < tmpOrders->size(); ++o)
	  { orderMap[tmpOrders->at(o).customer->index] = false; }
	     
	}

	dt_last = dt + 1;
    }

    if(nodeIdx_from == 0)
    { pathedMap.clear(); }

    if(nodeIdx_from == nodeIdx_to && nodeIdx_from == 0)
    { aRoute.push_back(0); dt += 1; continue; }

    if(nodeIdx_from == 0 || nodeIdx_from != nodeIdx_to)
    {
      std::vector<int> *tmpRoute = nodes[nodeIdx_from].routeTo(nodeIdx_to);
      for(int j = 0; j < tmpRoute->size(); ++j)
      {
	if(j < tmpRoute->size() - 1)
	{ aRoute.push_back(tmpRoute->at(j)); }

	//配達完了にする
	if(orderMap.find(tmpRoute->at(j)) != orderMap.end())
	{ orderMap.erase(tmpRoute->at(j)); }

	if(j < tmpRoute->size() - 1 && j == 3243433434)
	{
	    std::map<int, edgeClass> *aEdgeMap = &edgeMap[tmpRoute->at(j)];

	    for(auto oItr = orderMap.begin(); oItr != orderMap.end(); ++oItr)
	    {
		if(aEdgeMap->find(oItr->first) != aEdgeMap->end() && pathedMap.find(oItr->first) == pathedMap.end() &&
			tmpRoute->at(j + 1) != oItr->first)
		{
		    aRoute.push_back(oItr->first);
		    aRoute.push_back(tmpRoute->at(j));
		    pathedMap[oItr->first] = 1;
		    //orderMap.erase(oItr->first);
		    dt += aEdgeMap->at(oItr->first).dist * 2;
		}
	    }
	}
	if(j < tmpRoute->size() - 1 && tmpRoute->at(j) != 0)
	{ pathedMap[tmpRoute->at(j)] = 1; }
      }
      for(int j = 0; j < tmpRoute->size() - 1; ++j)
      { dt += GetDist(tmpRoute->at(j), tmpRoute->at(j + 1)); }

    }

    if(dt >= Tmax)
    { break; }
  }


  return error;

}


void outputRoute(std::vector<int> &aRoute)
{

  int preNode = 0;
  int time = 0;

  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    if(time >= Tmax)
    { break; }
    int thisNode = aRoute[i];

    if(thisNode == preNode)
    { 
      if(time < Tmax)
      { cout << "-1" << endl; } 
      ++time;
    }
    else 
    { 
      double dist = GetDist(preNode, thisNode);

      for(int j = 0; j < dist; ++j, ++time)
      { 
	if(time < Tmax)
	{ cout << thisNode + 1 << endl; }
      }
    }
    preNode = thisNode;

  }

  if(time < Tmax)
  { 
    for(int t = time; t < Tmax; ++t)
    { cout << "-1" << endl; }
  }

  return ;
}




Measured memory_bytes: 27916