【from new_dtoj 3970: graph】

题目描述

小f 的女朋友送给小f 一个有n个点m条边的无向图。但是这个无向图太大了，小f 的女朋友拿不动，于是小f 希望只保留图的一部分。在这张图上，对于第i条边ui,vi，从ui 到vi的代价为ai，从vi到ui的代价为bi。

小f 希望只保留一个包含1号点的有向环(不能有重复的点)，使得环上代价之和最小。

输入

第一行两个正整数表示n,m。

接下来m行，每行4个数，分别代表ui,vi,ai,bi。

输出

一行一个数，表示最小的代价。

样例输入

样例输入1

3 3

1 2 1 1000

2 3 1 1000

1 3 10000 1

样例输入2

13 15

1 2 5 5

2 3 10 10

3 4 5 5

4 5 100 100

5 6 20 20

6 7 17 17

7 2 15 15

5 9 2000 2000

9 10 8 8

10 11 7 7

11 12 8 8

12 13 7 7

13 8 8 8

8 9 7 7

1 12 10 10

样例输出

输出样例1

3

输出样例2

2089

提示

样例解释1

最小的环为1→2,2→3,3→1。

数据范围

对于前30%的数据，n,m≤50;

对于前75%的数据，n,m≤5000;

对于100%的数据，n≤3×1043×10^43×104,2≤m≤10510^5105,0≤ai,bi≤10410^4104。

题解：

最开始的想法，把1 号点拆成两个点，一个连全部的入边，一个连全部的出边，直接最短路。但这个算法明显错误，因为与1 号点相邻的点可能出现重复走的情况。所以就会想到说与1号点相连的点是起点/终点。于是可以暴力出哪一些点是起点，哪一些点是终点，然后求出$min(dist(1\to u)+dist(u\to v)+dist(v\to 1))$但是这样只能过30分（貌似可以卡常到65？）

但是事实上我们只需要分出一些情况，使得对于任意(u,v)

1.都当做是起点

2.都当做是终点

3.一个是起点，一个是终点

巧妙的二进制分组，也就是说因为对于任意的编号是不同的，所以枚举二进制位k，把第k位上是1的点当做起点，把为0的点当做终点，再反过来，把第k位上是0的点当做起点，把为1的点当做终点，这样所有的情况就都保证了

现在的问题在于每次分组，怎样只跑一遍最短路就可以就出$min(dist(1\to u)+dist(u\to v)+dist(v\to 1))$于是我们多加一个点，编号为n+1，从1连向u，从v连向n+1，所以问题就等价于求出1到n+1的最短路了

于是就只要走$logn$遍最短路

代码如下：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define _(d) while(d(isdigit(c=getchar())))#define I inlineusing namespace std;I int R(){    int x,f=1;char c;_(!)c=='-'?f=0:f;x=(c^48);    _()x=(x<<3)+(x<<1)+(c^48);return f?x:-x;}const int M=1e5+5,N=3e4+5;int n,m,h[N],V[M*2],W[M*2],nex[M*2],h2[N],c,t,tt,ans=1e9,d[N];bool vis[N];struct O{int x,y,a,b;}p[N];queue
        
         q;I void add(int u,int v,int w,bool ty){    V[++t]=v;W[t]=w;    if (ty) nex[t]=h[u],h[u]=t;    else nex[t]=h2[u];h2[u]=t;}I void S(){    for (int i=1;i<=n+1;i++) d[i]=1e9,vis[i]=0;    q.push(1);d[1]=0;vis[1]=1;    while(!q.empty()){        int x=q.front();q.pop();vis[x]=0;        for (int i=h[x];i;i=nex[i])            if (d[V[i]]>d[x]+W[i]){                d[V[i]]=d[x]+W[i];                if (!vis[V[i]]) q.push(V[i]),vis[V[i]]=1;            }        for (int i=h2[x];i;i=nex[i])            if (d[V[i]]>d[x]+W[i]){                d[V[i]]=d[x]+W[i];                if (!vis[V[i]]) q.push(V[i]),vis[V[i]]=1;            }    }    if (d[n+1]
         
          y) swap(x,y),swap(a,b); p[++tt]=(O){x,y,a,b}; } } c=t; for (int i=0;(1<
          
           <=n;i++){ memset(h2,0,sizeof(h2));t=c; for (int k,j=1;j<=tt;j++){ if ((1<