Delivery Boy - Codechef

This problem is part of the practice problems of the rating range 1600 to something like 1650, well if the concept is familiar and if you have even solved a single problem in this context then just a piece of cake for you. 

Basically, I feel that for the implementation part the problem had nothing cause it's just about writing the algo for floyd and then just accessing the costs for the mentioned stuff 1st for going to the restaurant one and then just directly to the food delivery and then just compare them and return the difference, although this is done from floyd warshall, I wonder if I could have used other stuff like dijkstra or bellman but it didn't make sense bcz the constraints were so low, but maybe I'll try using them.

They could have changed the way they were asking the solution or maybe the input stuff could have been list or sets instead of an adjacency mat. Then we would have been forced to go in the direction of Bellman or Dijkstra( mostly bellman ). But I feel that this would be if the problem would be a 1800 or 1900 kinda level 

Well, this one was quite useful if you looking for revising your DSA stuff or maybe you got an ADA exam on the horizon.

Explanation:-

The problem was quite straight forward, just apply Floyd Warshall that's what it was shouting you to do, if they would have given some other scenario or maybe would have kept some other condition then it would have been a lil bit tricky to spot or grok. Overall, the main idea is that we have to find the shortest costs from any 1 of the vertices to any other possible vertex, that will bring us to the next part of the problem where we just have to get the cost( that is time ) for going from restaurant to gas station + going from gas station to food delivery. And then just find the cost for going from restaurant directly to food delivery.

Code Implementation:-

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> floydWarshall(vector<vector<int>> vect){

    vector<vector<int>> temp(vect);

    int n=vect.size();

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

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

            for(int k=0;k<n;k++){

                temp[j][k]=min(temp[j][i]+temp[i][k],temp[j][k]);

            }

        }

    }

    return temp;

}

void printVect(vector<vector<int>> vect){

    int n=vect.size();

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

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

            cout<<vect[i][j]<<" ";

        }

        cout<<endl;

    }

}

int main() {

   

    int n;

    cin>>n;

    vector<vector<int>> vect(n);

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

        vector<int> temp(n);

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

            // int temp1;

            // cin>>temp1;

            cin>>temp[j];

            // temp.push_back(temp1);

        }

        vect[i]=temp;

    }

    vect=floydWarshall(vect);

    // printVect(vect);

    int m;

    cin>>m;

    int s,g,d;

   

    for(int i=0;i<m;i++){

        cin>>s>>g>>d;

        // Time taken when we have to first visit the Gas Station

        int time1=vect[s][g]+vect[g][d];

        cout<<time1<<" ";

        // Time which would have been taken in normal scenario

        int time2=vect[s][d];

        // Just print the difference between both

        cout<<abs(time1-time2)<<endl;

    }

   

    return 0;

}