如何加速dijkstra单一来源,单一目标与回溯？

Question

我试图解决A Dijkstra问题Alpha#20 Prob C并在案例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(而不是set),但我认为这不会对性能产生太大影响.

谢谢!

笔尖

Answer 1

你的解决方案对我来说似乎很好,O(E log V)因为这种限制绰绰有余.

您的问题很可能是由于您使用整数,特别是您使用的INT_MAX东西比任何可能的路径长度更大.随着10^5边缘和重量高达一百万int是不够的.一旦你溢出并获得负权重,所有dijkstra不变量都会中断,甚至不能保证终止.

将所有ints 替换为long longs,并INT_MAX使用大于s的替换10^11,并且您的解决方案很可能会通过.