三种堆分别是std::priority_queue pbds::priority_queue（pairing_heap_tag) zkw线段树（加入了剪枝,即modify函数里当兄弟节点的value比自己小的时候break，因为再往上的最小值肯定由兄弟节点贡献）
为什么没有手写的paring_heap和binary_heap？大概没人会手写吧 实际上是因为我不会
结论大概是
不开O2时的用时：zkw线段树 < pbds::pq < std::pq
开O2时：std::pq 远小于 zkw线段树 < pbds::pq（稠密图zkw线段树的速度跟std::pq相近 且pbds::pq快于std::pq（因为点数较小所以实际差别并不大））
鬼知道std::pq吸氧以后为什么会快那么多
//gen
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+7;
vector<int>G[MAXN];
inline void add(int u, int v) {
G[u].insert(lower_bound(G[u].begin(), G[u].end(), v), v);
}
char wbuf[50<<20], *p2 = wbuf;
inline void print(int x, int y, int z) {
static int sta[25], top; top = 0;
while(x) sta[++top] = x % 10, x /= 10;
while(top) *p2++ = sta[top--] + '0';
*p2++ = ' ';
while(y) sta[++top] = y % 10, y /= 10;
while(top) *p2++ = sta[top--] + '0';
*p2++ = ' ';
while(z) sta[++top] = z % 10, z /= 10;
while(top) *p2++ = sta[top--] + '0';
*p2++ = '
';
}
int main(void) {
freopen("data.in", "w", stdout);
mt19937 Rand((unsigned)(new char));
int n, m;
n = 3e5, m = 4e5;
printf("%d %d %d
", n, m, 1);
for(int i = 1; i < n; ++i) add(i, i+1);
for(int i = n; i <= m; ++i) {
int u, v;
do {
u = Rand()%n+1, v = Rand()%n+1;
} while(u == v || binary_search(G[u].begin(), G[u].end(), v));
add(u, v);
}
for(int i = 1; i <= n; ++i) {
for(auto it = G[i].begin(); it != G[i].end(); ++it) {
print(i, *it, Rand()%1000+1);
}
}
fwrite(wbuf, 1, p2 - wbuf, stdout);
return 0;
}
//runner
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
int main(void) {
system("g++ test.cpp -o test.exe -std=c++11");
system("g++ test.cpp -o testO2.exe -O2 -std=c++11");
system("g++ gen.cpp -o gen.exe -std=c++11");
while (1) {
printf("Case %d:
", ++cnt);
system("gen.exe");
puts("O2");
system("testO2.exe");
puts("Normal");
system("test.exe");
puts("");
}
return 0;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define mp make_pair
#define value first
#define mark second
const int MAXN = 3e5 + 7;
#define lson (o<<1)
#define rson (o<<1|1)
typedef pair<int, int> pii;
int dis[MAXN], head[MAXN], n, m, s, t, tot, vis[MAXN];
struct ZkwHeap {
pii Node[1 << 21];
int M;
inline void pushup(int o) {
Node[o] = Node[lson].value < Node[rson].value ? Node[lson] : Node[rson];
}
inline void build(int n) {
for (M = 1; M < n; M <<= 1);
for (int i = 1; i <= (M << 1) - 1; ++i)
Node[i].value = 0x3f3f3f3f;
for (int i = 1; i <= n; ++i) Node[i + M].mark = i, dis[i] = 0x3f3f3f3f;
}
inline int tpos() {return Node[1].mark;}
inline void modify(int pos, int val, bool flag) {
for (Node[pos += M].value = val; pos != 1; pos >>= 1) {
pushup(pos >> 1);
if (flag && Node[pos ^ 1].value < Node[pos].value) break;
}
}
inline int pop() {
int ret = Node[1].value;
modify(Node[1].mark, 0x3f3f3f3f, 0);
return ret;
}
} tree;
struct Edge {
int v, w, next;
} G[MAXN << 2];
inline void add(int u, int v, int w) {
G[++tot] = (Edge) {v, w, head[u]}; head[u] = tot;
}
std::priority_queue<pii, vector<pii>, greater<pii> >q;
typedef __gnu_pbds::priority_queue<pii, greater<pii>, pairing_heap_tag> heap;
heap::point_iterator it[MAXN];
heap q1;
unsigned long long ans[3];
void dijkstra(int s) {
for(int i = 1; i <= n; ++i) dis[i] = 0x3f3f3f3f;
dis[s] = 0;
q.push(mp(0, s));
while (!q.empty()) {
pii x = q.top(); int u = x.second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v, w, i = head[u]; i; i = G[i].next) {
v = G[i].v, w = G[i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (!vis[v]) q.push(mp(dis[v], v));
}
}
}
for (int i = 1; i <= n; ++i) ans[0] = (ans[0] + dis[i] * i);
}
void Dijkstra(int s) {
for(int i = 1; i <= n; ++i) dis[i] = 0x3f3f3f3f;
dis[s] = 0;
q1.push(mp(0, s));
while (!q1.empty()) {
pii x = q1.top(); int u = x.second; q1.pop();
for (int v, w, i = head[u]; i; i = G[i].next) {
v = G[i].v, w = G[i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (it[v] == 0) it[v] = q1.push(mp(dis[v], v));
else q1.modify(it[v], mp(dis[v], v));
}
}
}
for (int i = 1; i <= n; ++i) ans[1] = (ans[1] + dis[i] * i);
}
void DIjkstra(int s) {
tree.build(n);
tree.modify(s, 0, 0);
for (int u, v, w, k = 2; k <= n; ++k) {
dis[u = tree.tpos()] = tree.pop();
for (int i = head[u]; i; i = G[i].next) {
v = G[i].v, w = G[i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
tree.modify(v, dis[v], 1);
}
}
}
for (int i = 1; i <= n; ++i) ans[2] = (ans[2] + dis[i] * i);
}
char buf[50 << 20], *p1 = buf;
inline void read(int &x, int &y, int &z) {
x = y = z = 0;
while (!isdigit(*p1)) ++p1;
while (isdigit(*p1)) x = x * 10 + (*p1++) - '0';
while (!isdigit(*p1)) ++p1;
while (isdigit(*p1)) y = y * 10 + (*p1++) - '0';
while (!isdigit(*p1)) ++p1;
while (isdigit(*p1)) z = z * 10 + (*p1++) - '0';
}
int main(void) {
freopen("data.in", "r", stdin);
scanf("%d %d %d", &n, &m, &s);
fread(buf, 1, 50 << 20, stdin);
while (m--) {
int u, v, w;
read(u, v, w);
add(u, v, w);
}
double tim1 = clock();
dijkstra(1);
double tim2 = clock();
Dijkstra(1);
double tim3 = clock();
DIjkstra(1);
double tim4 = clock();
cerr << ans[0] << endl << ans[1] << endl << ans[2] << endl;
cerr << "std::pq " << (tim2 - tim1) << endl;
cerr << "pbds::pq " << (tim3 - tim2) << endl;
cerr << "zkwsgt " << (tim4 - tim3) << endl;
return 0;
}