【BZOJ】BZOJ3040 最短路线段树优化Dijkstra

题目描述

N个点，M条边的有向图，求点1到点N的最短路（保证存在）。 1<=N<=1000000，1<=M<=10000000

输入格式

第一行两个整数N、M，表示点数和边数。
第二行六个整数T、rxa、rxc、rya、ryc、rp。
前T条边采用如下方式生成：
1.初始化x=y=z=0。
2.重复以下过程T次：
x=(x*rxa+rxc)%rp;
y=(y*rya+ryc)%rp;
a=min(x%n+1,y%n+1);
b=max(y%n+1,y%n+1);
则有一条从a到b的，长度为1e8-100*a的有向边。
后M-T条边采用读入方式：
接下来M-T行每行三个整数x,y,z，表示一条从x到y长度为z的有向边。
1<=x,y<=N，0<z,rxa,rxc,rya,ryc,rp<2^31

输出格式

一个整数，表示1~N的最短路。

输入样例

3 3
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1

输出样例

提示

请采用高效的堆来优化Dijkstra算法。

分析

正解是配对堆优化Dijkstra，被我用线段树水过去了，写个博客记录一下模板

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005,maxm=20000005;
const long long oo=1e18;
int T,n,m,rxa,rxc,rya,ryc,rp;
long long dis[maxn],A[maxn];int bit[maxn<<2];
int ecnt,info[maxn],nx[maxm<<1],v[maxm<<1],w[maxm<<1];
void add(int u1,int v1,int w1){nx[++ecnt]=info[u1];info[u1]=ecnt;v[ecnt]=v1;w[ecnt]=w1;}
void build(int id,int l,int r)
{
    register int mid=(l+r)/2;
    bit[id]=mid;if(l==r){A[mid]=oo;return;}
    build(id<<1,l,mid);build(id<<1|1,mid+1,r);
}
void fix(int id,int l,int r,int k,long long val)
{
    if(l==r){A[k]=val;return;}
    register int mid=(l+r)/2,lc=id<<1,rc=id<<1|1;
    k<=mid?fix(lc,l,mid,k,val):fix(rc,mid+1,r,k,val);
    bit[id]=A[bit[lc]]<A[bit[rc]]?bit[lc]:bit[rc];
}
void DIJK()
{
    for(register int i=1;i<=n;i++)dis[i]=oo;
    dis[1]=0;build(1,1,n),fix(1,1,n,1,0);
    for(register int i=1;i<=n;i++)
    {
        register int nw=bit[1];fix(1,1,n,nw,oo);
        for(int i=info[nw];i;i=nx[i])if(dis[v[i]]>dis[nw]+w[i])
        fix(1,1,n,v[i],dis[v[i]]=dis[nw]+w[i]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d%d%d",&T,&rxa,&rxc,&rya,&ryc,&rp);
    for(int i=1,x=0,y=0,a,b;i<=T;add(a,b,1e8-100*a),i++)
        x=(1ll*x*rxa+rxc)%rp,y=(1ll*y*rya+ryc)%rp,
        a=min(x%n+1,y%n+1),b=max(y%n+1,y%n+1);
    for(int i=T+1,u1,v1,w1;i<=m;add(u1,v1,w1),i++)
        scanf("%d%d%d",&u1,&v1,&w1);
    DIJK();
    printf("%lld
",dis[n]);
}