我在这个问题上应用贾克斯特拉的算法有什么错误呢？

Question

问题链接如下：http://www.spoj.com/problems/FPOLICE/

达马卡·辛格(一个骗子)刚刚抢劫了一家银行，他想尽快离开这个国家。但有个小问题，警察！在他出国的路上，他必须经过一些警察局。每个警察局都有一定的风险(对于Dhamaka Singh)。他想在一定的时间内到达机场，否则他就赶不上飞机了。他还想走一条将与之相关的总风险降到最低的道路。帮助Dhamaka Singh离开这个国家。

输入

输入的第一行包含一个整数t，测试用例数。测试用例紧随其后。

每个测试案例的第一行包含两个整数N (3 <= N 100)和T (1 <= T <= 250)，分别表示警察局的数量和他到达机场的总时间。

达马卡·辛格必须从第一个警察局出发，到达第一个警察局(机场就在第Nth派出所之后)。你可以认为从第Nth警察局到机场的时间是可以忽略不计的。

接下来是N行，每一行都有N个数，用单个空格分隔。所有的数字都用一个空格分隔开。第1行中的jth整数表示从第一警察局到达jth警察局所需的时间。

接下来是另一个N行，每一行都有N个数。所有的数字都用一个空格分隔开。第一条线中的jth整数表示从第一警察局到jth派出所所涉及的风险。

输出

对于每个测试用例输出，一行包含由单个空格分隔的2个整数。

第一个整数表示到达机场的最小总风险。第二个整数表示以最小总风险到达机场所需的最短时间。

如果不可能在时间T(包括)到达机场，只需打印"-1“(引号明确)。

我使用的算法如下：

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.

我的代码如下：

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});
                        }
                    }
                }
            }
        }
    }
}

现在，在为问题中的示例输入运行上述代码时，即，

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

但是，我的输出结果是，7 3

我只想知道，我在这个问题上使用贾克斯特拉是正确的，还是我错了？如果没有错的话，我的执行工作又会有什么问题呢？谢谢!

PS:为了避免混乱，我省略了这里的图书馆。

Answer 1

如果您简单地修复了初始化visited时的错误，那么您的代码适用于该测试用例：

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

对于其他测试用例，我不确定您的代码是非常低效率，还是在某些情况下是错误的。