正边权无向图,一条边两个方向权值不一定相同,求经过点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 ;
}
05-11 15:10