bzoj4398: 福慧双修

正边权无向图，一条边两个方向权值不一定相同，求经过点1的最小简单环

简单环包含了点1的一条出边和一条入边，且这两条边不同，因此可以枚举这两条边的编号的二进制表示中哪一位不同，用最短路求此时的最优解，时间复杂度$O(mlog^2m)$

#include<bits/stdc++.h>

using std::swap;

using std::vector;

using std::priority_queue;

const int N=,inf=;

int _(){

    int x=,c=getchar();

    while(c<)c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x;

}

int n,m;

struct edge{

    int to,v;

    bool operator<(edge e)const{return v>e.v;}

};

int l[N],ans=inf;

priority_queue<edge>q;

vector<edge>es[N],eS,eT;

bool ed[];

void mins(int&a,int b){if(a>b)a=b;}

void cal(){

    q=priority_queue<edge>();

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

    for(int i=;i<eS.size();++i)if(ed[i]){

        edge w=eS[i];

        if(l[w.to]>w.v)q.push((edge){w.to,l[w.to]=w.v});

    }

    while(q.size()){

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

        if(w.v>=ans)break;

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

        for(int i=;i<es[w.to].size();++i){

            edge u=es[w.to][i];

            if(l[u.to]>w.v+u.v)q.push((edge){u.to,l[u.to]=w.v+u.v});

        }

    }

    for(int i=;i<eT.size();++i)if(!ed[i]){

        edge w=eT[i];

        mins(ans,l[w.to]+w.v);

    }

}

int main(){

    n=_(),m=_();

    for(int i=,a,b,v1,v2;i<m;++i){

        a=_(),b=_(),v1=_(),v2=_();

        if(a==b)continue;

        if(a==||b==){

            if(b==)swap(a,b),swap(v1,v2);

            eS.push_back((edge){b,v1});

            eT.push_back((edge){b,v2});

        }else{

            es[a].push_back((edge){b,v1});

            es[b].push_back((edge){a,v2});

        }

    }

    for(int t=;t<eS.size();t<<=){

        for(int i=;i<eS.size();++i)ed[i]=i&t;

        cal();

        for(int i=;i<eS.size();++i)ed[i]^=;

        cal();

    }

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

    return ;

}