BZOJ 4398: 福慧双修

菩萨为行，福慧双修，智人得果，不忘其本。
——唐朠立《大慈恩寺三藏法师传》
有才而知进退，福慧双修，这才难得。
——乌雅氏
如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有 N 块区域，M 条小路，两块区域之间可通过小路连接起来。现在甄嬛站在 1 号区域，而她需要在御花园中绕一绕，且至少经过 1 个非 1 号区 域的区域。但是恰好 1 号区域离碎玉轩最近，因此她最后还是要回到 1 号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。

Input

第一行仅 2 个正整数 n,m，意义如题。 接下来 m 行每行 4 个正整数 s,t,v,w，其中 s,t 为小路所连接的两个区域的编号，v 为甄嬛从 s 到 t 所需的时间，w 为甄嬛从 t 到 s 所需的时间。数据保证无重边。

Output

仅一行，为甄嬛回到 1 号区域所需的最短时间，若方案不存在，则输出-1

Sample Input

3 3
1 2 2 3
2 3 1 4
3 1 5 2

Sample Output

8

Solution

一条合法路径一定是 $1\to a\to \dots\to b\to 1$ 这样的。
考虑 a 和 b 一定有至少一个二进制位不同。
所以按二进制分组，每次新建一个源点和汇点，分别连向某位为 1 和 0 的点，然后跑最短路。

Code

#include<bits/stdc++.h>

#define mp(a,b) std::make_pair(a,b)

int n,p[40001],dis[40001];
bool vis[40001];
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,
    std::greater<std::pair<int,int> > >q;

struct edge
{
    int to,ne,w;
}e[200001];

inline void add(int i,int a,int b,int w)
{
    e[i].to=b,e[i].ne=p[a],e[i].w=w,p[a]=i;
}

inline void yjq(int andv,int anda,int &ans)
{
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for(int j=p[1];j;j=e[j].ne)
        if((e[j].to&andv)==anda)
            q.push(mp(dis[e[j].to]=e[j].w,e[j].to));
    while(!q.empty())
    {
        int k=q.top().second;q.pop();
        if(vis[k])continue;
        vis[k]=1;
        for(int j=p[k];j;j=e[j].ne)
            if(e[j].to==1)
            {
                if((k&andv)!=anda&&ans>dis[k]+e[j].w)ans=std::min(ans,dis[k]+e[j].w);
            }
            else if(dis[e[j].to]>dis[k]+e[j].w)
            {
                q.push(mp(dis[e[j].to]=dis[k]+e[j].w,e[j].to));
            }
    }
}

int main()
{
    int m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(i*2+1,a,b,c);
        add(i*2+2,b,a,d);
    }
    int ans=0x7fffffff;
    for(int i=1;i<=n;i<<=1)
    {
        yjq(i,i,ans);
        yjq(i,0,ans);
    }
    printf("%d",ans);
}

日期： 2016-12-26

标签： BZOJ 最短路

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/158/ 查看。