c++ - 在将 dijkstra 算法应用于此时，我究竟该如何处理以下情况？

Question

所以，我正在解决以下问题:http://www.spoj.com/problems/ROADS/en/

N 个以数字 1 ... N 命名的城市与单行道相连。每条道路都有两个与之关联的参数:道路长度和道路需要支付的通行费(以硬币数量表示)。 Bob 和 Alice 曾经住在城市 1。在发现 Alice 在他们喜欢玩的纸牌游戏中作弊后，Bob 与她分手并决定搬走 - 搬到城市 N。他想尽快到达那里可能，但他缺钱。我们想帮助 Bob 找到从城市 1 到城市 N 的最短路径，并且他有钱可以负担得起。

输入

输入以测试用例的数量 t 开始。然后是 t 个测试用例。每个测试用例的第一行包含整数 K，0 <= K <= 10000，Bob 可以在路上花费的最大硬币数。第二行包含整数N，2 <= N <= 100，城市总数。第三行包含整数R，1 <= R <= 10000，道路总数。以下 R 行中的每一行通过指定由单个空白字符分隔的整数 S、D、L 和 T 来描述一条道路:S 是源城市，1 <= S <= N D 是目的地城市，1 <= D <= N L是道路长度，1 <= L <= 100。T是通行费(以硬币数表示)，0 <= T <= 100 注意，不同的道路可能有相同的起点和终点城市。

输出

对于每个测试用例，输出单行包含从城市 1 到城市 N 的总通行费小于或等于 K 个硬币的最短路径的总长度。如果该路径不存在，则输出-1。

现在，我所做的是，我尝试为此使用 djikstra 算法，如下所示:

我不是只有一个节点作为状态，而是 节点和硬币作为一个状态，然后应用 dijkstra。 长度是状态之间的权重。 我在不超过硬币总数的情况下将长度最小化。

我的代码如下:

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

class node
{
public:
    int vertex;
    int roadlength;
    int toll;
};

int dist[101][101]; // for storing roadlength
bool visited[101][10001];
int cost[101][101]; // for storing cost
int ans[101][10001]; // actual distance being stored here
void djikstra(int totalcoins, int n);

bool operator < (node a, node b)
{
    if (a.roadlength != b.roadlength)
        return a.roadlength < b.roadlength;
    else if (a.toll != b.toll)
        return a.toll < b.toll;
    return a.vertex < b.vertex;
}

int main (void)
{
    int a,b,c,d;
    int r,t,k,n,i,j;
    cin>>t;
    while (t != 0)
    {
        cin>>k>>n>>r;
        for (i = 1; i <= 101; i++)
            for (j = 1; j <= 101; j++)
                dist[i][j] = INT_MAX;

        for (i = 0; i <= n; i++)
            for (j = 0; j <= k; j++)
                ans[i][j] = INT_MAX;

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

        for (i = 0; i < r; i++)
        {
            cin>>a>>b>>c>>d;
            if (a != b)
            {
                dist[a][b] = c;
                cost[a][b] = d;
            }
        }
        djikstra(k,n);
        int minlength = INT_MAX;
        for (i = 1; i <= k; i++)
        {
            if (ans[n][i] < minlength)
                minlength = ans[n][i];
        }
        if (minlength == INT_MAX)
            cout<<"-1\n";
        else
            cout<<minlength<<"\n";
        t--;
    }
    cout<<"\n";
    return 0;
}

void djikstra(int totalcoins, int n)
{
    set<node> myset;
    myset.insert((node){1,0,0});
    ans[1][0] = 0;
    while (!myset.empty())
    {
        auto it = myset.begin();
        myset.erase(it);
        int curvertex = it->vertex;
        int a = it->roadlength;
        int b = it->toll;
        if (visited[curvertex][b] == true)
            continue;
        else
        {
            visited[curvertex][b] = true;
            for (int i = 1; i <= n; i++)
            {
                if (dist[curvertex][i] != INT_MAX)
                {
                    int foo = b + cost[curvertex][i];
                    if (foo <= totalcoins)
                    {
                        if (ans[i][foo] >= ans[curvertex][b] + cost[curvertex][i])
                        {
                            ans[i][foo] = ans[curvertex][b] + cost[curvertex][i];
                            myset.insert((node){i,ans[i][foo],foo});
                        }
                    }
                }
            }
        }
    }
}

现在，我有两个疑惑:

1. 首先，对于问题的第一个给定测试用例，我的输出不正确，即

   示例输入:

   2
   5
   6
   7
   1 2 2 3
   2 4 3 3
   3 4 2 4
   1 3 4 1
   4 6 2 1
   3 5 2 0
   5 4 3 2
   0
   4
   4
   1 4 5 2
   1 2 1 0
   2 3 1 1
   3 4 1 0
   
   Sample Output:
   11
   -1
   

我的输出结果是，4 -1 这对于第一个测试用例是错误的。我哪里出错了？

1. 如何处理具有多个边的情况？也就是说，问题提到，注意不同的道路可能有相同的源城市和目的地城市。我如何处理这种情况？

Answer 1

存储道路的简单方法是作为 vector 的 vector 。对于每个起源城市，您都希望拥有从该城市通往的所有道路的 vector 。

因此，当您处理发现的通往某个城市的“最佳”路径时，您将遍历从该城市出发的所有道路，看看它们是否可能是通往其他城市的“最佳”路径。

如前所述，您有两个相互作用的“最佳”定义，不能简单地合并为一个定义。最短的更重要，因此“最佳”的主要定义是最短的，仅在平局的情况下考虑最便宜的。但是您还需要仅考虑最便宜的“最佳”的替代定义。

正如我针对另一个问题所建议的那样，您可以对“最佳”的主要定义进行排序，这样您始终可以先处理该定义中较好的路径，然后再处理较差的路径。然后，您需要针对“最佳”的第二个定义跟踪迄今为止所见的最佳路径，以便您仅在第二个定义中的处理路径与第一个定义优先处理的路径相比不佳时，才从处理路径中剔除。