bzoj5109: [CodePlus 2017]大吉大利，晚上吃鸡！

Description

最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。在游戏中，皮皮
和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。当然，有些时候并不能堵桥，皮皮和毛
毛会选择在其他的必经之路上蹲点。K博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并
不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战士很感兴趣。【题目描述】游戏的地图
可以抽象为一张n个点m条无向边的图，节点编号为1到n，每条边具有一个正整数的长度。假定大魔王都会从S点出
发到达T点（S和T已知），并且只会走最短路，皮皮和毛毛会在A点和B点埋伏大魔王。
为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定A点和B点必须满足：
1.大魔王所有可能路径中，必定会经过A点和B点中的任意一点
2.大魔王所有可能路径中，不存在一条路径同时经过A点和B点
K博士想知道，满足上面两个条件的A,B点对有多少个，交换A,B的顺序算相同的方案

Input

第一行输入四个整数n,m,S,T(1≤n≤5×10^4,1≤m≤5×10^4,1≤S,T≤n)，含义见题目描述。
接下来输入m行，每行输入三个整数u,v,w(1≤u,v≤n,1≤w≤10^9)表示存在一条长度为w的边链接u和v。
1≤n≤5×10^4,1≤m≤5×10^4,1≤w≤10^9

Output

输出一行表示答案

求出S-T最短路图，以及传递闭包

任选一个以T为根的树形图，对每条非树边u->v，选一个随机数x，将v的父亲和u分别到根的路径异或上x

若S和T不联通，任选两个点

否则，可以选两个点，使得其中一个点不在最短路图上，另一个点为最短路图上点权为0的点，或者选最短路图上两个互不能到达且权值相同且非零的点

#include<bits/stdc++.h>

typedef long long i64;

typedef unsigned long long u64;

typedef unsigned int u32;

const int N=5e4+;

char ib[N*],*ip=ib;

int _(){int x;scanf("%d",&x);return x;}

int n,m,S,T,e0[N],ep=;

i64 l[N],ans=;

struct edge{

    int to,v,nx;

}e[N*];

struct node{

    int w;

    i64 l;

    bool operator<(const node&w)const{return l>w.l;}

};

std::priority_queue<node>q;

bool ed[N];

struct pos{

    int w;

    u64 v,l;

    bool operator<(const pos&x)const{return v!=x.v?v<x.v:l>x.l;}

}ps[N];

u64 f[N];

int fa[N],pp=,cp=;

u32 su[N][N/+];

void f1(int w){

    ed[w]=;

    for(int i=e0[w];i;i=e[i].nx){

        int u=e[i].to;

        if(l[u]+e[i].v==l[w]){

            if(!ed[u])fa[u]=w,f1(u);

            else{

                u64 z=rand();

                z=z<<^rand();

                f[w]^=z;

                f[fa[u]]^=z;

            }

        }

    }

}

int _get(u32*a,int x){return a[x>>]>>x&;}

void _set(u32*a,int x){a[x>>]|=<<x;}

void _or(u32*a,u32*b){

    int p=n/+;

    for(int i=;i<p;i+=){

        a[i]|=b[i];

        a[i+]|=b[i+];

        a[i+]|=b[i+];

        a[i+]|=b[i+];

    }

}

void f2(int w){

    _set(su[w],w);

    ed[w]=;

    for(int i=e0[w];i;i=e[i].nx){

        int u=e[i].to;

        if(l[u]+e[i].v==l[w]){

            if(ed[u])f2(u),f[w]^=f[u];

            _or(su[w],su[u]);

        }

    }

    if(f[w])ps[pp++]=(pos){w,f[w],l[w]};

    else ++cp;

}

void cal(){

    f1(T);

    f2(T);

    std::sort(ps,ps+pp);

    for(int i=,j=;i<pp;i=j){

        int t=;

        for(++j;j<pp&&ps[i].v==ps[j].v;++j)t+=_get(su[ps[i].w],ps[j].w);

        ans+=i64(j-i-t)*t;

    }

    ans+=cp*i64(n-cp-pp);

    printf("%lld\n",ans);

}

int main(){

    n=_();m=_();S=_();T=_();

    srand(n^m^S^T^);

    for(int i=;i<m;++i){

        int a=_(),b=_(),c=_();

        e[ep]=(edge){b,c,e0[a]};e0[a]=ep++;

        e[ep]=(edge){a,c,e0[b]};e0[b]=ep++;

    }

    for(int i=;i<=n;++i)l[i]=1ll<<;

    q.push((node){S,l[S]=});

    while(q.size()){

        node w=q.top();q.pop();

        if(w.l!=l[w.w])continue;

        if(w.w==T)return cal(),;

        for(int i=e0[w.w];i;i=e[i].nx){

            int u=e[i].to;

            if(l[u]>w.l+e[i].v)q.push((node){u,l[u]=w.l+e[i].v});

        }

    }

    printf("%lld\n",n*i64(n-)/);

    return ;

}

bzoj5109: [CodePlus 2017]大吉大利，晚上吃鸡！的相关教程结束。