c++ - 如何加速 dijkstra 单源、单目标回溯？

Question

我正在尝试解决 A Dijkstra 问题 Alpha #20 Prob C并在 Case 31 上获得 TLE，它有 100000 节点和 99999 边。我假设我的代码的复杂度为 O(E lg V)，大约为 499995。我认为它足够快，但由于结果不成功，我通过使用内联代码进行回溯和一些优化(例如在目标节点从队列中删除后立即中断 dijkstra)来加快速度。我认为这不会影响结果，就像删除一个节点一样，这意味着找到了最佳路径，我们可以继续享受了。我现在已经没有优化此代码的想法，因此来到这里。代码如下:

#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
#include <climits>
#include <limits>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vii> vvii;

vi D;
vi parent;
vi path;
vvii graph;


void dijkstra(int i, int j)
{
        set<ii> Q;
        Q.insert(ii(0, i));
        D[i] = 0; parent[i] = -555;
        bool checked = false;
        while(!Q.empty())
        {
                ii top = *Q.begin();
            Q.erase(Q.begin());
            int topnode = top.second;
            for(vii::iterator it = graph[topnode].begin();it != graph[topnode].end();it++)
            {
                int v = it->first, d2 = it->second;
                if(D[v] > D[topnode] + d2)
                    {
                        if(D[v] != INT_MAX)
                        {
                                Q.erase(Q.find(ii(D[v], v)));
                        }
                        D[v] = D[topnode] + d2; parent[v] = topnode;
                        Q.insert(ii(D[v], v));
                        if(v == j)
                                checked = true;
                    }
            }
            if(checked)
            {
                if(Q.find(ii(D[j], j)) == Q.end())
                    break;
            }
        }
}

/* void backtrack(int n)
{
    if(parent[n] != -555)
    {
        path.push_back(n);
        backtrack(parent[n]);
    }
}

void backtrack2(int n)
{
    while(parent[n] != -555)
    {
        path.push_back(n);
        n = parent[n];
    }
} */

int main(void) {
    int n, m, x, y, z;
    scanf("%d%d", &n, &m);
    graph.clear(); graph.resize(n); D.resize(n, INT_MAX); parent.resize(n, -1);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        graph[x-1].push_back(ii(y-1, z));
        graph[y-1].push_back(ii(x-1, z));
    }
    dijkstra(0, n-1);
    if(D[n-1] == INT_MAX)
        printf("-1\n");
    else
    {
        int x = n-1;
        while(parent[x] != -555)
        {
            path.push_back(x);
            x = parent[x];
        }
        printf("1 ");
        for(int i = int(path.size())-1;i >= 0;i--)
        {
            printf("%d ", path[i]+1);
        }
        printf("\n");
    }
}

我不确定我可以做些什么来提高它的速度。我已经尝试减少递归调用的开销以及更多可能的开销。如果有人有任何其他想法，或者可以指出某种错误(如果有的话(在优化中))，我们将不胜感激。现在我认为唯一可以做的就是使用 priority_queue(而不是设置)，但我认为这不会对性能产生太大影响。

谢谢!

Nib

Answer 1

您的解决方案对我来说似乎基本没问题，O(E log V) 对于这个约束来说绰绰有余。

您的问题很可能是由于您使用整数这一事实，特别是您使用 INT_MAX 作为大于任何可能路径长度的东西。 10^5 边和权重高达一百万 int 是不够的。一旦溢出并获得负权重，所有 dijkstra 不变量都会失效，甚至不能保证终止。

将所有 int 替换为 long long，并将 INT_MAX 替换为大于 10^11 的值，您的解决方案很可能会通过。