SPFA It's not omnipotent to find the shortest path . Heap optimization in dense graph dijkstra More efficient :

typedef pair<int,int> pii;
priority_queue<pii, vector<pii>, greater<pii> > q
void dijkstra(){
memset(dis,10,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[K]=0;
q.push(make_pair(dis[K],K));
while(!q.empty()){
pii tmp=q.top();q.pop();
int node=tmp.second;
if(vis[node])continue;
vis[node]=1;
for(int i=LINK[node];i;i=e[i].next)
if(dis[e[i].y]>dis[node]+e[i].v){
dis[e[i].y]=dis[node]+e[i].v;
q.push(make_pair(dis[e[i].y],e[i].y));
}
}
}

Heap optimized Dijkstra More articles about

  1. POJ1797 Heavy Transportation ( Heap optimized Dijkstra deformation )

    Background Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand bus ...

  2. Plain and heap optimized dijkstra And the plain version prim Algorithm comparison

    1.dijkstra Time complexity :O(n^2) n Sub iteration , Every time we find the distance set S The shortest point Each iteration uses the points found t To update other points to S The shortest distance . #include<iostream> #inclu ...

  3. Learning notes &#183; Heap optimization $\mathscr{dijkstra}$

    I was forced to learn this algorithm today -- In fact, for learning graph theory, my heart is rejected \(\mathscr{qnq}\) Because of the discovery about this \(\mathscr{SPFA}\) Time complexity of \(O(kE)\) Medium \(k \ap ...

  4. JZYZOJ1525 HAOI2012 road Heap optimized dijkstra+pair

    From Tyvj Guest *[haoi2012] road                 describe Description     C State-owned n city , Between cities m A one-way road connects . A path is called the shortest path , When ...

  5. Heap optimized dijkstra Algorithm

    #include<bits/stdc++.h> using namespace std; #define ll long long #define P pair<int,int> ...

  6. 【 Templates 】 Heap optimized dijkstra

    Life algorithm , In case you forget #include<bits/stdc++.h> using namespace std; int head[200005],dis[200005],n,m,s,f,g, ...

  7. 【Dijkstra Heap optimization 】 Luogu P2243 Circuit maintenance

    Background Elf Is from Gliese Girl of the planet , Drifting to the earth by accident . When she was helpless , Good transporter Mark and James Took her in .Elf Thank you very much Mark and James, But I haven't been able to give ...

  8. POJ-2387.Til the Cows Come Home.( Five ways :Dijkstra + Dijkstra Heap optimization + Bellman-Ford + SPFA + Floyd-Warshall)

    I just finished learning the shortest path algorithm yesterday , Today I began to practice and found that I am a real dish , I can't remember how the adjacency table is written , It's the truth of the dish ...... To make up for your own food , I decided to write this question in five ways , And in Dijkstra Algorithm heap optimization in addition ...

  9. Luogu P4779 【dijkstra】+( Heap optimization )+( Chain forward star ) ( The template questions )

    < Topic link > Title Description Given a  N  A little bit , M  Graphs with nonnegative weights with directed edges , Please calculate from  S  set out , The distance to each point . The data guarantee that you can get from  S  Starting at any point . Input format : The first line is three positive integers  N,M, ...

Random recommendation

  1. fnciton

    -----oracle Separate field characters as a temporary table select column_value as site_id from table (select fn_split_clob(dashboard_pr ...

  2. [No00005F] Reading and mind

    Read thousands of books , travelling , Not enough … You have to have a interlocutor with you , It's more interesting . On the night of October 7th , Talk to friends about reading , Live online , Three hundred people , Four hours of conversation , joy ! Part1: The carrier of reading It exudes the strongest fragrance of knowledge and the most meaningful history under the inscription ...

  3. Skillfully use Javascript Medium slice()

    slice() yes Javascript in Array One way , The definition is . arrayObject.slice(start,end) The function is to extract from the original array start To end Position intercepts a new array , The return value is ...

  4. static and const keyword

    C# And C++ Of static There are two uses : In process oriented programming static And in object-oriented programming static. The former applies to ordinary variables and functions , There are no classes involved   Process oriented Static global variables Static global variables are declared in the entire file ...

  5. Keras RetinaNet github Project installation

    In the repository Directory /keras-retinanet/ in , perform pip install . --user after , There is an error : D:\>cd D:\JupyterWorkSpace\keras-retinane ...

  6. Selenium-java Test environment construction

    1.1 background Selenium It's also a Web Tools for application testing .Selenium Test runs directly in browser , It's like a real user is doing it . Supported browsers include IE.Mozilla Firefox.Mozilla ...

  7. csrf_token Cross site request settings

    $.ajaxSetup({ data: {csrfmiddlewaretoken: '{{ csrf_token }}' }, }); <form> {% csrf_token %} &l ...

  8. c--socket signal communication TCP piece

    https://www.cnblogs.com/ashen/p/4474360.html #include <sys/socket.h> 2 #include <stdlib.h&g ...

  9. linux avoid crontab The execution output of fills the disk directory ? User mail Take up a lot of space ?

    Requirements describe : It was set up in the morning ntp The client's timing task , I find that there are more and more You have new mail in /var/spool/mail/root This hint . then , Just look at the specific documents , because ntpdate It's every minute ...

  10. Codeforces 670D1. Magic Powder - 1 violence

    D1. Magic Powder - 1 time limit per test: 1 second memory limit per test: 256 megabytes input: stand ...