## current position：Home>Dijkstr heap optimization

# Dijkstr heap optimization

2022-08-06 08:55:20【ThXe】

```
typedef pair<int, int> PII;
const int N = 1e6 + 10;
struct DIJKSTRA {
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void init() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(int s,int end)
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({
0, s });
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({
dist[j], j });
}
}
}
if (dist[end] == 0x3f3f3f3f) return -1;
return dist[end];
}
void output() {
cout << dijkstra(1, n) << endl;
}
}Dij;//mlogn
```

copyright notice

author[ThXe],Please bring the original link to reprint, thank you.

https://en.chowdera.com/2022/218/202208060847341565.html

## The sidebar is recommended

- C language (recursive) uses the recursive method to solve x ^ n
- 【SSL】2021-08-18 1370. Salesman's problem
- 202109-3 impulsive neural network
- The first training before 2021 CSP - Mathematics
- Niuke little white moon race 40
- Niuke Xiaobai monthly race 39 "a", "B", "C", "d", "e", "g", "H"
- AtCoder Beginner Contest 223
- P1094 [noip2007 popularity group] souvenir grouping (double pointer)
- Combinatorics - 01 permutation and combination
- Ee5407: space time wireless communication

## guess what you like

[cf] Codeforces Round ＃762 (Div. 3)

Yet another minimization problem (number theory / DP / 01)

Shortest path problem

Simple nonsense questions (Group backpack)

Sumsets (challenge programming competition)

[haoi2016] character merging - interval + shape pressure DP + analysis

The 10th Blue Bridge Cup group B provincial competition - equal difference series

[template question] breadth first traversal of trees and graphs

Blue bridge sum of squares - Enumeration | bisection | hash

Blue bridge sum of squares - Enumeration | bisection | hash

## Random recommended

- Acwing 1214 wave series
- Application conditions of coppersmith theorem in RSA
- Celebration party (multiple backpacks)
- 【acwing】854. Floyd finds the shortest path*
- [Luogu] p1507 NASA's Food Program & p1910 l country's combat spy & p1855 extract kkksc03 (two-dimensional value 01 backpack)
- [NEFU discrete] discrete mathematics homework in 2020 / topics over the years
- Codeforces round 768 (Div. 2) C. and matching
- OJ: the journey of the top 100 up Masters
- Single source sink shortest path problem (Dijkstra)
- C language Fibonacci sequence, find the nth Fibonacci number
- [bzoj 5127] data verification (fooling around)
- Codeforces Round ＃764 (Div. 3)
- Codeforces training
- Solution to the third training of GXNU training team
- [Blue Bridge Cup] 1227 Chocolate * (2 points)
- Acwing week 25
- Training - complex DP
- 2021 group programming ladder competition - problem solution
- GCD vs LCM (number theory / thinking)
- ＃1137 N-th Tribonacci Number
- Untitled-5
- [pat class A] 1072 gas station (Dijkstra, enumeration)
- Fibonacci sequence
- Acwing--849. Dijkstra finding the shortest path I
- [TIANTI race] l3-005 dustbin distribution (heap optimized version Dijkstra)
- [Luogu P1300] urban street transportation fee system [DFS]
- [atcoder beginer contest 252] partial solution
- Chapter 1: simplify the same code decimal sum s (D, n)
- Chapter 1: find the algebraic sum of odd factors, find the same decimal sum s (D, n), simplify the same code decimal sum s (D, n), expand the same code decimal sum s (D, n)
- Codeforces Round ＃804 C The Third Problem
- Game improvement of smart people: example of lesson 2: Tongtong's mathematical problems (Fen)