BZOJ2069 POI2004ZAW（最短路）

时间：2023-03-08 17:28:06

　　显然这样的路径一定是选择了与1相邻的不同的两点分别作为起点和终点（除1本身）。如果能将每一组起点终点都计算到就可以得出最优解了。暴力显然不行。注意到我们每次求出的是单源最短路径，考虑如何充分利用信息。那么有一种神奇的方法：按照编号的二进制的某一位给所有与1相邻的点分组，一组作为起点另一组作为终点，然后断掉所有由1到终点的边并跑以1为起点的单源最短路。这样可以得到该情况下的最优答案。并且如果对于每一位都这样操作，注意到任意两点的编号二进制下肯定存在一位不同，那么其一定会在某一次时被分进两组统计入答案。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

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

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 5010

#define M 20010

#define inf 700000000

int n,m,p[N],d[N],t=-,ans=inf;

bool flag[N];

struct data{int to,nxt,len;

}edge[M];

struct data2

{

    int x,d;

    bool operator <(const data2&a) const

    {

        return d>a.d;

    }

};

priority_queue<data2> q;

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

void dijkstra()

{

    while (!q.empty()) q.pop();

    memset(d,,sizeof(d));d[]=;q.push((data2){,});

    memset(flag,,sizeof(flag));

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

    {

        while (!q.empty()&&flag[q.top().x]) q.pop();

        if (q.empty()) break;

        data2 v=q.top();q.pop();

        flag[v.x]=;

        for (int j=p[v.x];~j;j=edge[j].nxt)

        if (v.d+edge[j].len<d[edge[j].to])

        {

            d[edge[j].to]=v.d+edge[j].len;

            q.push((data2){edge[j].to,d[edge[j].to]});

        }

    }

}

void solve(int t,int op)

{

    for (int i=p[];~i;i=edge[i].nxt)

    if (op^((edge[i].to&t)>)) edge[i].len+=inf;

    dijkstra();

    for (int i=p[];~i;i=edge[i].nxt)

    if (op^((edge[i].to&t)>)) edge[i].len-=inf,ans=min(ans,d[edge[i].to]+edge[i^].len);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2069.in","r",stdin);

    freopen("bzoj2069.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

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

    memset(p,,sizeof(p));

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

    {

        int x=read(),y=read(),w=read(),v=read();

        addedge(x,y,w),addedge(y,x,v);

    }

    t=;

    while (t<=n) solve(t,),solve(t,),t=t<<;

    cout<<ans;

    return ;

}

相关文章