小编Nal*_*waj的帖子

我试图解决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 = …