【BZOJ4398】福慧双修 题解（建图优化）

题目链接

题目大意：给定一张$n$个点$m$条边的无向图，每条边两个方向的权值不一定相同。问从$1$出发不重复走一条边回到$1$的最短路径。

-------------------

暴力不太会。大概是$dfs$？复杂度不得上天……

正解：对于那些端点不是$1$的边，因为要走最短路，所以这些边只会走一次，所以对答案是没有影响的。考虑端点为$1$的边，我们进行“二进制分组”。每次按照二进制分为两组：入边和出边，然后跑最短路。路径长为$dis[edge[i].to]$加上入边权值。这样做能把所有情况包括进去，符合最优性质。

时间复杂度$O(n\log^2 n)$。

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,vis[],dis[],tag[],ans=0x3f3f3f3f;

int head[],cnt=-;

struct edge

{

    int next,to,dis;

}edge[];

struct node

{

    int dis,pos;

    bool operator < (const node &x) const

    {

        return x.dis<dis;

    }

};

priority_queue<node> q;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void add(int from,int to,int dis)

{

    edge[++cnt].next=head[from];

    edge[cnt].to=to;

    edge[cnt].dis=dis;

    head[from]=cnt;

}

inline void dijkstra()

{

    for(int i=;i<=n;i++) dis[i]=0x3f3f3f3f;

    memset(vis,,sizeof(vis));

    dis[]=;q.push((node){,});

    while(!q.empty())

    {

        node tmp=q.top();q.pop();

        int now=tmp.pos;

        if (vis[now]) continue;

        vis[now]=;

        for (int i=head[now];i!=-;i=edge[i].next)

        {

            if (tag[i]==-) continue;

            int to=edge[i].to;

            if (dis[to]>dis[now]+edge[i].dis)

            {

                dis[to]=dis[now]+edge[i].dis;

                if (!vis[to]) q.push((node){dis[to],to});

            }

        }

    }

    for (int i=head[];i!=-;i=edge[i].next)

        if (tag[i]==-&&ans>dis[edge[i].to]+edge[i^].dis)

            ans=dis[edge[i].to]+edge[i^].dis;

}

signed main()

{

    n=read(),m=read();

    memset(head,-,sizeof(head));

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

    {

        int u=read(),v=read(),w1=read(),w2=read();

        add(u,v,w1);add(v,u,w2);

    }

    for (int d=;d>=;d--)

    {

        for (int i=head[];i!=-;i=edge[i].next)

            if((i>>d)&) tag[i]=,tag[i^]=-;

            else tag[i]=-,tag[i^]=;

        dijkstra();

        for (int i=head[];i!=-;i=edge[i].next)

            if ((i>>d)&) tag[i]=-,tag[i^]=;

            else tag[i]=,tag[i^]=-;

        dijkstra();

    }

    printf("%lld",(ans==0x3f3f3f3f)?-:ans);

    return ;

}