Where am I going wrong in applying Djikstra's algorithm in this?

Question

The problem link is as follows: http://www.spoj.com/problems/FPOLICE/

Dhamaka Singh (a crook) has just robbed a bank and would like to get out of the country as soon as possible. But there is a slight problem, the police! On his way out of the country he has to pass through some police stations. Each police station has a certain risk (for Dhamaka Singh) associated with it. He wants to get to the airport within a certain time T or else he'll miss his flight. He also wants to take a path that minimizes the total risk associated with it. Help Dhamaka Singh get out of the country.

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

The first line of each test case contains 2 integers N (3 <= N 100) and T (1 <= T <= 250), denoting the number of police stations and the total time he has to reach the airport, respectively.

Dhamaka Singh has to start from the first police station and reach the Nth one (the airport is just after the Nth police station). You can consider the time taken between the Nth police station and the airport to be negligible.

Next there are N lines with N numbers in each line, separated by single spaces. All numbers are separated by a single space. The jth integer in the ith line represents the time taken to reach the jth police station from the ith police station.

Next there are another N lines with N numbers in each line. All numbers are separated by a single space. The jth integer in the ith line represents the risk involved in travelling to the jth police station from the ith police station.

Output

For each test case output one line containing 2 integers separated by a single space.

The first integer denotes the minimum total risk to reach the airport. The second integer denotes the minimum time required to reach the airport at the minimum total risk.

If it is impossible to reach the airport within time T (inclusive), just print "-1" (quotes for clarity).

The algorithm I used is as follows:

Instead of only having a single node as the state, I take
node and time as one state and then apply dijkstra.
risk is the weight between the states.
and I minimize the risk without exceeding the time limit.

My code is as follows:

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair


class node
{
public:
    int vertex;
    int risk;
    int timeval;
};

void djikstra (int t, int n);
int timetaken[101][101];
int risk[101][101];
int dist[101][251];  // shows the current calculated risk
bool visited[101][251];

bool operator < (node a, node b)
{
    if (a.risk != b.risk)
        return a.risk < b.risk;
    if (a.timeval != b.timeval)
        return a.timeval < b.timeval;
    return a.vertex < b.vertex;
}

int main (void)
{
    int t,n,total;
    cin>>t;
    while (t != 0)
    {
        cin>>n>>total;
        for ( int i = 1; i <= 101; i++ )
            for ( int j = 1; j <= 251; j++ )
                dist[i][j] = INT_MAX;

        for ( int i = 0; i <= n; i++ )
            for ( int j = 0; j <= t; j++ )
                visited[i][j] = false;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin>>timetaken[i][j];

        for (int i = 1; i <= n; i++)
            for ( int j = 1; j <= n; j++)
                cin>>risk[i][j];

        djikstra(total,n);
        int mintime = INT_MAX;
        int minrisk = INT_MAX;
        for (int i = 1; i <= total; i++) // checking for the final destination
        {
            if (dist[n][i] < minrisk)
            {
                minrisk = dist[n][i];
                mintime = i;
            }
        }
        if (minrisk != INT_MAX)
            cout<<minrisk<<" "<<mintime<<"\n";
        else
            cout<<"-1"<<"\n";
        t--;
    }
    return 0;
}

void djikstra (int t, int n)
{
    set<node> myset;  // using a set for djikstra's
    myset.insert((node){1,0,0}); // inserting the source node
    dist[1][0] = 0;
    while (!myset.empty())
    {
        auto it = myset.begin();
        myset.erase(myset.begin());
        int u = it->vertex;
        int curtime = it->timeval;
        int currisk = it->risk;
        if (visited[u][curtime] == true)
            continue;
        else
        {
            visited[u][curtime] = true;
            for (int i = 1; i <= n; i++ )
            {
                if ( i != u )
                {
                    int foo = curtime + timetaken[u][i];
                    if (foo <= t)
                    {
                        if (dist[i][foo] >= dist[u][curtime] + risk[u][i])
                        {
                            dist[i][foo] = dist[u][curtime] + risk[u][i];
                            myset.insert((node){i,dist[i][foo],foo});
                        }
                    }
                }
            }
        }
    }
}

Now, on running the above code for the sample input in the question, i.e.,

Sample Input:
1
4 10
0 6 2 3
6 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

Sample Output:
4 9

However, my output comes out as, 7 3

I just wish to know am I right in applying Djikstra in this question, or am I wrong? And if not wrong, where am I going wrong in my implementation? Thanks!

PS: I have omitted the libraries here to avoid cluttering.

Answer 1

Your code works for that test case if you simply fix the bug in initializing visited should be:

for ( int i = 0; i <= n; i++ )
    for ( int j = 0; j <= total; j++ )
        visited[i][j] = false;

For other test cases, I'm not sure whether your code is just horribly inefficient or whether in some cases it would be wrong.