[BZOJ4398] 福慧双修

题面感人。。。

求从1号点出发，经过至少另一个点，走的边不重复的最小简单环。

发现对于简单环上和1号点相接的两个点的二进制表示上一定有至少一位不一样。

我们就把它二进制分组，然后在dij的时候就可以看看当前的to如果是1的话现在的点如果是分在出发点区域的就不行。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=40005;
struct Node {int id,dis;bool operator < (const Node &rhs) const {return dis>rhs.dis;}};
priority_queue<Node>q;
int n,m,dis[N],ans,head[N],ecnt;
struct Edge{int to,nxt,val;}e[N*5];
void add(int bg,int ed,int val) {e[++ecnt]=(Edge){ed,head[bg],val};head[bg]=ecnt;}
void dij(int a,int b) {
    memset(dis,0x3f,sizeof dis);
    for(int i=head[1];i;i=e[i].nxt) 
        if((e[i].to&a)==b) q.push((Node){e[i].to,e[i].val}),dis[e[i].to]=e[i].val;
    while(!q.empty()) {
        Node u=q.top();q.pop();
        if(u.dis!=dis[u.id]) continue;
        for(int i=head[u.id];i;i=e[i].nxt) {
            if(e[i].to==1) {
                if((u.id&a)!=b)ans=min(ans,dis[u.id]+e[i].val); 
                continue;
            }
            if(dis[u.id]+e[i].val<dis[e[i].to]) dis[e[i].to]=dis[u.id]+e[i].val,q.push((Node){e[i].to,dis[e[i].to]});
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,c,d;i<=m;i++) 
        scanf("%d%d%d%d",&a,&b,&c,&d),add(a,b,c),add(b,a,d);
    ans=0x3f3f3f3f;
    for(int i=1;i<=n;i<<=1) {
        dij(i,i);
        dij(i,0);
    }
    cout<<ans;
    return 0;
}