STL 使用新姿势 get √

Problem

就是求单源最短路。
$n\leq 1e6, m\leq 1e7, 5s$

Solution

hzw 的博客学过来的～

事实证明手写配对堆 + 指针 + 静态内存池分配耗时 >pbds pairing heap

我觉得我还是写 pbds 算了...

Code

// Code by ajcxsu
// Problem: dijkstra

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

char ch;
template<typename T> inline void gn(T &x) {
    ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-48, ch=getchar();
}

const int N=1e6+10, M=1e7+10;
int h[N], to[M], nexp[M], p=1;
ll W[M];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
struct mpair {
    ll first;
    int second;
} ;
inline bool operator <(const mpair &a, const mpair &b) { return a.first>b.first; }
typedef __gnu_pbds::priority_queue<mpair,less<mpair>,pairing_heap_tag> heap;
heap pq;
heap::point_iterator id[N];

ll dist[N];
char S[N];

int main() {
    int n, m, t, tt;
    int rxa, rxc, rya, ryc, rp, x, y, z;
    gn(n), gn(m), gn(t), gn(rxa), gn(rxc), gn(rya), gn(ryc), gn(rp), tt=t;
    x=y=z=0;
    int u, v;
    while(tt--) {
        x=((ll)x*rxa+rxc)%rp;
        y=((ll)y*rya+ryc)%rp;
        u=min(x%n+1,y%n+1);
        v=max(y%n+1,y%n+1);
        ins(u, v, 100000000-100*u);
    }
    int w;
    for(int i=0;i<m-t;i++) gn(u), gn(v), gn(w), ins(u, v, w);
    for(int i=1;i<=n;i++) dist[i]=10000000000000000ll;
    dist[1]=0;
    pq.push({0,1});
    int na;
    while(!pq.empty()) {
        na=pq.top().second, pq.pop();
        if(S[na]) continue;
        S[na]=1;
        if(na==n) printf("%lld\n", dist[n]), exit(0);
        for(int u=h[na];u;u=nexp[u])
            if(!S[to[u]] && dist[to[u]]>dist[na]+W[u]) {
                dist[to[u]]=dist[na]+W[u];
                if(id[to[u]]!=0) pq.modify(id[to[u]], {dist[to[u]], to[u]});
                else id[to[u]]=pq.push({dist[to[u]], to[u]});
            }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-3040.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆