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

现在，我有两个疑惑：

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

Sample Input:

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 这对于第一个测试用例是错误的。我哪里错了？

如何处理多边的情况？也就是说，问题提到，Notice that different roads may have the same source and destination cities.我该如何处理这种情况？

Answer 1

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

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

和以前一样，您有两个 "best" 的交互定义，不能简单地组合成一个定义。最短的更重要，所以 "best" 的主要定义是最短的，仅在平局的情况下考虑最便宜的。但是您还需要 "best" 的替代定义，只考虑最便宜的。

正如我针对另一个问题所建议的那样，您可以对 "best" 的主要定义进行排序，这样您始终可以在处理较差的路径之前处理该定义中较好的路径。然后，您需要跟踪迄今为止为 "best" 的第二个定义所看到的最佳路径，以便您仅在第二个定义中从第一个定义优先处理的已处理路径中删除处理路径。

Answer 2

我没有读过你的代码，但我可以告诉你这个问题不能用未经修改的 Dijkstra 算法解决。

这个问题至少和二进制一样难knapsack problem。如何？这个想法是在规定的问题中构建背包问题。由于已知背包问题在多项式时间内无法解决，因此上述问题也不是。由于Dijkstra算法是多项式算法，因此无法应用。

考虑具有一组 D 个值 X 和一个最大值 m = max(X) 的二进制背包问题。现在构造提出的问题：

假设有 D + 1 个城市，城市 n 通过两条道路与城市 n + 1 相连。让城市 1 到 D 唯一对应于 X 中的值 v。让这样一个城市 n 的两条路只去城市 n + 1，一条路花费 v 距离 m - v + 1，另一条路花费 0 距离m + 1.

本质上，"you get exactly what you pay for" -- 您每花费一个硬币，您的行程就会缩短一个单位的距离。

这将问题重新定义为 "what's the maximum Bob can spend by only spending money either no or one time on each toll?" 这与我们开始的二进制背包问题相同。

因此，如果我们解决了上述问题，我们也可以解决二元背包问题，因此，与二元背包问题相比，上述问题不能再"efficient"解决了——用 Dijkstra 算法是.

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

How exactly can I handle the following condition while applying dijkstra's algorithm to this?

c++

algorithm

dijkstra