在将dijkstra的算法应用于此时，我如何处理下列条件？
因此，我正在解决以下问题：http://www.spoj.com/problems/ROADS/en/
编号1的城市..。N与单程公路相连.每条道路都有两个相关参数:道路长度和道路收费(以硬币数表示)。鲍勃和爱丽丝过去住在城市1号。发现爱丽丝在他们喜欢玩的纸牌游戏中作弊后，鲍勃和她分手了，决定搬到城里去。他想尽快赶到那里，但他缺钱。我们想帮助鲍勃找到从第一座城市到N市的最短道路，这条路他有足够的钱可以负担得起。
输入
输入以测试用例的数目t开始。然后再进行测试用例。每个测试用例的第一行包含整数K，0 <= K <= 10000，最大数量的硬币，鲍勃可以花在他的路上。第二行包含整数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到总收费小于或等于K硬币的城市N的最短路径的总长度。如果不存在这种路径，则输出-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 2 2 2 4 3 3 3 4 4 4 1 4 2 2 2 3 5 5 3 2 0 5 4 3 2 4 4 4 2 4 4 4 2 4 4 4 2 4 4 4 2 2 2 1 2 2 2 3 3 3 1 3 4 1 4 4 1 4 4 1 4 4 1 4 4 1 4 4 4 2 2 2 3 4 4 4 1 4 4 4 2 2 2 3 4 4 4 2 2 2 3 4 4 4 6 1 5 5 3 3 2 3 4 4 4 2 2 2 3 4 4 4 2 2 2 3 3 3 4 4 4 2 2 2 5 5 4 3 3 3 4 4 4 1 4 4 4 2 2 2 5 4 3 3 4 4 4
我的输出结果是，4 -1，这对于第一个测试用例是错误的。我这是怎么回事？
- 如何处理多个边的情况？也就是说，问题提到，
Notice that different roads may have the same source and destination cities.如何处理这个条件？
回答 2
Stack Overflow用户
发布于 2015-11-02 17:56:57
存储道路的简单方法是作为矢量向量。对于每一个起源城市，你想有一个向量的所有道路从该城市。
因此，当你处理一条被发现的“最好”的城市道路时，你会遍历从那个城市到其他城市的所有道路，看看它们是否是其他城市的“最佳”路径。
和前面一样，您有两个相互作用的“最佳”定义，不能简单地组合成一个定义。最短是更重要的，所以“最好”的主要定义是，只有在关系最便宜的情况下才考虑最短。但是，考虑到最便宜的情况，你也需要“最佳”的替代定义。
正如我为另一个问题建议的那样，您可以对“最佳”的主要定义进行排序，因此您总是在处理更糟糕的路径之前处理该定义中更好的路径。然后，您需要跟踪“最佳”的第二个定义到目前为止所看到的最优路径，以便只在第二个定义中没有更好的路径时从处理路径中从第一个定义优先处理的路径中删除路径。
Stack Overflow用户
发布于 2015-11-02 18:08:42
我还没有读过您的代码，但是我可以告诉您，这个问题不能用Dijkstra算法的未经修改的版本来解决。
这个问题至少和二进制背包问题一样困难。多么?其思想是在所述问题中构造背包问题。由于背包问题在多项式时间内是不可解的，所以它也不是所描述问题的解，因此Dijkstra算法是多项式算法，因此不能应用。
考虑具有一组D、多个值、X和最大值m = max(X)的二进制背包问题。现在将建议的问题构建为这样：
假设有D + 1城市，城市n通过两条道路连接到城市n + 1。让城市通过1通过D唯一地对应于X中的值v。从这样的城市n只允许两条路到城市n + 1，一条用距离m - v + 1来计算v，另一条用m + 1的距离来计算0。
本质上，“你得到了你所付出的”--每花一枚硬币，你的旅程就会缩短一个单位的距离。
这就重新定义了一个问题：“鲍勃每次只花一次或不花一次钱，能花多少钱？”这和我们开始讨论的二进制背包问题是一样的。
因此，如果我们解决指定的问题，我们也可以解决二进制背包问题，因此所述问题不能比二进制背包问题更“有效”-- Dijkstra的算法是。
https://stackoverflow.com/questions/33483606
复制相似问题
腾讯云开发者
