FISHER - Fishmonger

A fishmonger wants to bring his goods from the port to the market. On his route he has to traverse an area with many tiny city states. Of course he has to pay a toll at each border.

Because he is a good business man, he wants to choose the route in such a way that he has to pay as little money for tolls as possible. On the other hand, he has to be at the market within a certain time, otherwise his fish start to smell.

Input

The first line contains the number of states n and available time t. The first state is the port, the last state is the market. After this line there are n lines with n numbers each, specifying for each state the travel time to the i-th state. This table is terminated with an empty line. The table of the tolls follows in the same format.

n is at least 3 and at most 50. The time available is less than 1000. All numbers are integers.

There are many test cases separated by an empty line. Input terminates with number of states and time equal 0 0.

Output

For each test case your program should print on one line the total amount of tolls followed by the actual travelling time.

Example

Sample input:
4 7
0 5 2 3
5 0 2 3
3 1 0 2
3 3 2 0

0 2 2 7
2 0 1 2
2 2 0 5
7 2 5 0

0 0

Sample output:
6 6

This corresponds to the following situation, the connections are labeled with (time, toll):

 

###################################editorial###################################

   in this problem we can apply bfs or dfs ..  we need to keep track of two parameter time and cost 

  at same instant .. so we use a 2d array visited[node_no][time_used]<-- this matrix contain the minimum cost needed to reach node_no with time_used if there is any attempt to revisit the same node with  same time and more cost then do not push node in to queue..

QUEUE -->>  queue contain 3 parameters [node no ]  [time ] [cost]..  

each time when reach to the last node ie nth node then check  final cost and final time and if less then  previos final cost then update final cost and final time ..

############################CODE###############################################

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

int main()

 {

  // freopen("abc.txt","r",stdin);

 

  int n,t;

  while(1)

     {

      int visited[60][1010];

      cin>>n>>t;

     

       

      for(int i=0;i<n;i++)

       {

        for(int j=0;j<1010;j++)

         visited[i][j]=INT_MAX;

       }

     

      if(n==0 && t==0 )break;

      int cost[100][100];

      int time[100][100];

      for(int i=0;i<n;i++)

       {

         

         for(int j=0;j<n;j++)

          {

           

           

            cin>> time[i][j]

           

          }

       }

           for(int i=0;i<n;i++)

            {

            for(int j=0;j<n;j++)

             {

              cin>>cost[i][j]

             }

            }

       

     

      queue<pair<pair<int,int>,int> >s;// node,time,cost

      s.push(make_pair(make_pair(0,0),0));

      visited[0][0]=0; // since we can visit 1st vertix  with cost 0 and time 0

       

     

      int anst=INT_MAX,ansc=INT_MAX;

      while(!s.empty())

       {

          int start=s.front().first.first;

          int cu=s.front().second;

          int tu=s.front().first.second;

          s.pop();

           

          for(int i=0;i<n;i++)// checking all vertices adjecent to start

           {

              if(visited[i][tu+time[start][i]]>cu+cost[start][i] && i!=start && tu+time[start][i]<=t)

                   // checking if node we r going to visit have already visited with same time in minimiu       //cost or not if yes then do not visit again since already visited with   more efficient cost and less time

               {

                     

                      visited[i][tu+time[start][i]]=cu+cost[start][i];

                 s.push(make_pair(make_pair(i,tu+time[start][i]),cu+cost[start][i]));

                   

                 if(i==n-1)// if last node then update ans if possible 

                  {

                   if(ansc>cu+cost[start][i])

                    {

                      ansc=cu+cost[start][i];

                      anst=tu+time[start][i];

                    }

                  }

                 

                 

               }

           }

       

       

       

       

       }

      cout<<ansc<<" "<<anst<<endl;

    }

 

 }