/category/zd/ zh-CN Mon, 26 Dec 2016 10:48:00 +0800 Mon, 26 Dec 2016 10:48:00 +0800 /archives/158/ /archives/158/ Mon, 26 Dec 2016 10:48:00 +0800 admin ###Description 菩萨为行，福慧双修，智人得果，不忘其本。 ——唐朠立《大慈恩寺三藏法师传》 有才而知进退，福慧双修，这才难得。 ——乌雅氏 如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有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->a->...->b->1这样的 考虑a和b一定有至少一个二进制位不同 所以按二进制分组，每次新建一个源点和汇点，分别连向某位为1和0的点，然后跑最短路 ###Code ```c++ #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); } ``` ]]> 0 /archives/158/#comments /feed/archives/158/