TLE в Dijkstra Codeforces

Question

Я только что изучил алгоритм Дейкстры и решил несколько проблем, и я пытаюсь решить эту проблему http://codeforces.com/problemset/problem/20/C, но я получаю ограничение по времени Превышено в большом тестовом примере, я хочу знать, может ли мой код еще более оптимизироваться в любом случае, или если есть еще одна более быстрая реализация Дейкстры, тогда дайте мне знать.
Мой код

#include<bits/stdc++.h> 

using namespace std; 
#define pii pair<int,int> 
#define vp vector<pii> 

int p[100010],d[100010]; 

void printer(int current) 
{ 
    if(p[current]==-2) 
    { 
     printf("%d ",current); 
     return; 
    } 
    printer(p[current]); 
    printf("%d ",current); 
} 

class Prioritize 
{ 
    public: 
    int operator()(const pii &p1,const pii &p2) 
    { 
     return p1.second<p2.second; 
    } 
}; 

int main() 
{ 
    priority_queue<pii, vp, Prioritize> Q; 
    int nv; 
    scanf("%d",&nv); 
    vp g[nv+1]; 
    int ne,u,v,w; 
    scanf("%d",&ne); 
    for(int i=0;i<ne;i++) 
    { 
     scanf("%d %d %d",&u,&v,&w); 
     g[u].push_back(pii(v,w)); 
     g[v].push_back(pii(u,w)); 
    } 

    int source=1; 
    int size; 
    for(int i=1;i<=nv;i++) 
    { 
     d[i]=INT_MAX; 
     p[i]=-1; 
    } 
    d[source]=0; 
    p[source]=-2;//marker for source. 
    Q.push(pii(source,d[source])); 
    while(!Q.empty()) 
    { 
     u=Q.top().first; 
     Q.pop(); 
     size=g[u].size(); 
     for(int i=0;i<size;i++) 
     { 
      v=g[u][i].first; 
      w=g[u][i].second; 
      if(d[v]>d[u]+w) 
      { 
       d[v]=d[u]+w; 
       p[v]=u; 
       Q.push(pii(v,d[v])); 
      } 
     } 
    } 
    /*for(int i=1;i<=nv;i++) 
    { 
     printf("Node %d and min weight = %d and parent = %d\n",i,d[i],p[i]); 
    }*/ 
    if(p[nv]==-1) 
    { 
     printf("%d\n",-1); 
     return 0; 
    } 
    printer(nv); 
    return 0; 
} 

Answer 1

Ваш алгоритм имеет сложность O(nm). Я предлагаю добавить следующую

Q.push(pii(source,d[source])); 
    while(!Q.empty()) 
    { 
     u=Q.top().first; 
     int curD = Q.top().second; //this 
     if(curD > d[u]) continue; //and this 
     Q.pop(); 
     size=g[u].size(); 
     for(int i=0;i<size;i++) 
     { 

После сложности изменений будет O(mlogn). Если вы сейчас русский, вы можете прочитать http://e-maxx.ru/algo/dijkstra_sparse