我在哪里应用 Djikstra 的算法会出错？

Question

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

Dhamaka Singh（骗子）刚刚抢劫了一家银行，想尽快离开这个国家。但是有个小问题，警察！在他出国的路上，他必须经过一些警察局。每个警察局都有一定的风险（对 Dhamaka Singh 而言）。他想在特定时间 T 内到达机场，否则他将错过航班。他还想走一条将与之相关的总风险降至最低的道路。帮助 Dhamaka Singh 离开这个国家。

输入

输入的第一行包含一个整数t，测试用例的数量。接下来是 t 个测试用例。

每个测试用例的第一行包含2个整数N（3 <= N 100）和T（1 <= T <= 250），表示派出所的数量和他到达的总时间分别是机场。

Dhamaka Singh 必须从第一个警察局出发，到达第 N 个（机场就在第 N 个警察局之后）。你可以认为从第N个派出所到机场的时间可以忽略不计

接下来有 N 行，每行有 N 个数字，由单个 space 分隔。所有数字都由一个 space 分隔。第i行第j个整数表示从第i个派出所到第j个派出所所用的时间。

接下来还有N行，每行有N个数字。所有数字都由一个 space 分隔。第i行第j个整数表示从第i个派出所前往第j个派出所的风险。

输出

对于每个测试用例，输出一行包含 2 个由单个 space.

分隔的整数

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

如果无法在时间 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

我只是想知道我在这个问题上应用Djikstra是对的还是错的？如果没有错，我在实施过程中哪里出错了？谢谢！

PS：为了避免混乱，我省略了这里的库。

Answer 1

如果您只是修复初始化中的错误，您的代码适用于该测试用例 visited 应该是：

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

对于其他测试用例，我不确定您的代码是否效率低得可怕，或者在某些情况下是否会出错。

我在哪里应用 Djikstra 的算法会出错？

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

c++

algorithm

dijkstra