Description：

给定一张无向图，每条边从两个方向走各有一个权值，求从点 $1$ 往出走至少一步之后回到点 $1$ 且不经过一条边多次的最短路。

$1\le n \le 5000$

Solution：

路径肯定是从起点出发，经过起点临集中的，在到起点临集中的另一个点，在返回起点。先记下所有与 $1$ 节点相邻的点到 $1$ 节点的距离，然后把一节点从图中删去，问题就变成了在一个图中选两个标记的点他们之间的距离加上这两个点的标记最小值，暴力枚举其中一个求 $dijkstra$ 是 $O(n^2\log n)$ 的。

于是考虑不枚举一个，而是同时枚举很多个，即将带标记的点划分为两个集合，把一个集合带权加入堆中在另一个集合更新最小值，由于方向不同长度不同所以要正反跑两边，这样只要最终更新的两个点在一次被划分为两个集合就能取到最终答案，关键问题在于如何划分。

我们可以按照二进制划分，即枚举每一个二进制位，将 $0$ 和 $1$ 划分为不同集合，这样任意两个不同的数一定至少有一位不同，一定在一次划分中被分成两半。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 5010

#define MAXM 10010

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,v;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	return;

}

bool v[MAXN];

int dis[MAXN];

int main()

{

    memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

    int a,b,c,d;

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

    {

        scanf("%d%d%d%d",&a,&b,&c,&d);

        add(a,b,c);add(b,a,d);

    }

    priority_queue< pair<int,int> > q;

    int ans = INF;

    for(int b = 0;b <= 13;++b)

    {

        memset(dis,0x3f,sizeof(dis));

        for(int i = lin[1];i != -1;i = e[i].nxt)

        {

            if(e[i].to & (1 << b))

            {

                q.push(make_pair(-e[i].v,e[i].to));

                dis[e[i].to] = e[i].v;

            }

        }

        memset(v,false,sizeof(v));

        v[1] = true;

        while(!q.empty())

        {

            int k = q.top().second;q.pop();

            if(v[k])continue;

            v[k] = true;

            for(int i = lin[k];i != -1;i = e[i].nxt)

            {

                if(dis[e[i].to] > dis[k] + e[i].v)

                {

                    dis[e[i].to] = dis[k] + e[i].v;

                    q.push(make_pair(-dis[e[i].to],e[i].to));

                }

            }

        }

        for(int i = lin[1];i != -1;i = e[i].nxt)

        {

            if((e[i].to & (1 << b)) == 0)

            {

                ans = min(ans,dis[e[i].to] + e[i ^ 1].v);

            }

        }

        memset(dis,0x3f,sizeof(dis));

        for(int i = lin[1];i != -1;i = e[i].nxt)

        {

            if((e[i].to & (1 << b)) == 0)

            {

                q.push(make_pair(-e[i].v,e[i].to));

                dis[e[i].to] = e[i].v;

            }

        }

        memset(v,false,sizeof(v));

        v[1] = true;

        while(!q.empty())

        {

            int k = q.top().second;q.pop();

            if(v[k])continue;

            v[k] = true;

            for(int i = lin[k];i != -1;i = e[i].nxt)

            {

                if(dis[e[i].to] > dis[k] + e[i].v)

                {

                    dis[e[i].to] = dis[k] + e[i].v;

                    q.push(make_pair(-dis[e[i].to],e[i].to));

                }

            }

        }

        for(int i = lin[1];i != -1;i = e[i].nxt)

        {

            if(e[i].to & (1 << b))

            {

                ans = min(ans,dis[e[i].to] + e[i ^ 1].v);

            }

        }

    }

	cout << ans << endl;

	return 0;

}