T2 洞穴zaw

【问题描述】

在 Byte 山的山脚下有一个洞穴入口. 这个洞穴由复杂的洞室经过隧道连接构成. 洞穴的入口是 1 号点.两个洞室要么就通过隧道连接起来,要么就经过若干隧道间接的相连. 现在决定组织办一个'King's of Byteotia Cup' 比赛. 参赛者的目标就是任意选择一条路径进入洞穴并尽快出来即可. 一条路径必须经过除了 1 之外还至少要经过其他一个洞室.一条路径中一个洞不能重复经过(除了 1 以外),类似的一条隧道也不能重复经过.

一个著名的洞穴探险家 Byteala 正准备参加这个比赛. Byteala 已经训练了数月而且他已获得了洞穴系统的一套详细资料. 对于每条隧道他都详细计算了从两个方向经过所需要的时间. 经过一个洞室的时间很短可以忽略不记. 现在Byteala 向计算一条符合条件的最优路径.

【输入格式】

第一行有两个数 n 和 m (3 <= n <= 5000, 3 <= m <= 10000) 分别表示洞室的数目以及连接他们的隧道的数目. 洞室从 1 到 n 编号. “前面洞室”的编号为 1.接下来 m 行描述了所有的隧道. 每行四个整数 a,b,c,d 表示从洞室 a 到洞室 b 需要 c 分钟的时间,而从洞室 b 到洞室 a 需要 d 分钟的时间, 1 <= a,b <= n, a <> b, 1 <=c,d <= 10000. 你可以假设符合要求的路径肯定存在.

【输出格式】

输出一行,最少需要多少时间完成比赛.

【样例输入】

3 3

1 2 4 3

2 3 4 2

1 3 1 1

【样例输出】

【说明】

经过 1,2,3,1

Solution

来源:POI2004,Bzoj2069

①O(n^2logn)

从1点出发枚举会走到哪条边哪到哪个点,将这条边回边标为不可选,从那个点跑向1的最短路即可.

因为有些奇奇怪怪的剪枝,它会跑的非常快(0.08s即可,与正解差不了多少).

剪枝:

普通单源单汇的最短路剪枝,Dijskra算法,当前更新的最小点为汇点可直接输出
枚举的那条边>=ans直接不枚举
当前最小点+W[i](枚举的那条边)>=ans可以退出
到达的点>=ans可以不入队

②%DJ两遍最短路 nlogn

一条边相当与四条边,为什么呢?双向×走法(直+倒)

edge u→v w[1]=w1(直) w[2]=w2(倒)

edge v→u w[1]=w2(直) w[2]=w1(倒)

我们拿每条边w[1](标记v→w不能)从1跑最短路,第二遍用w[2]跑,这样是从1倒着走回到其他点,相当与从其它点走过来.

统计一下每个点两次答案之和即可.

对于从一出发的边标记颜色,到达的点的最短距离来自哪条边为哪个

最后统计答案,d[i](正)→d1[i](负)两点颜色不同.注意,与一号点相连的点可正反,因为一号点可走过多次。

Code

①

// <zaw.cpp> - Thu Oct  6 08:17:54 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <queue>

#define INF 1e9

#define IN inline

#define RG register

using namespace std;

typedef long long LL;

inline int gi() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

const int N=,M=N<<;

int n,m,t,ans;int d[N],fr[N];int to[M],ne[M],W[M];bool u[N];

struct node{

    int s,p;

    bool operator<(node a)const{return s>a.s;}

};

priority_queue<node>q;

IN void link(RG int u,RG int v,RG int w){

    to[++t]=v;ne[t]=fr[u];fr[u]=t;W[t]=w;

    //if(u==1)cout<<v<<endl;this

}

void read(){

    n=gi(),m=gi();

    while(m--){

        int u=gi(),v=gi(),w=gi(),w1=gi();

        link(u,v,w);link(v,u,w1);

    }

}

IN int Dij(RG int begin,RG int end,int w){

    for(int i=;i<=n;i++)d[i]=INF;

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

    memset(u,,sizeof(u));

    while(!q.empty()){

        while(u[q.top().p]&&!q.empty())q.pop();

        if(q.empty())break;

        int x=q.top().p;q.pop();u[x]=;

        if(w+d[x]>=ans)break;//this

        if(x==end)return d[];

        for(int o=fr[x],y;y=to[o],o;o=ne[o])

            if(d[x]+W[o]<d[y]){

                d[y]=d[x]+W[o];

                if(d[y]>=ans)continue;//this

                q.push((node){d[y],y});

            }

    }

    return d[];

}

void Work(){

    read();ans=INF;

    for(int i=fr[],w;i;i=ne[i]){

        if(W[i]>=ans)continue;//this

        if(i&)w=W[i+],W[i+]=INF;else w=W[i-],W[i-]=INF;

        ans=min(ans,W[i]+Dij(to[i],,W[i]));

        if(i&)W[i+]=w;else W[i-]=w;

    }

    printf("%d",ans);

}

int main()

{

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

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

    Work();

    return ;

}

②dj's code

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#define in long long

using namespace std;

in getint(){

    in res=,f=;char c=getchar();

    while(c!='-' &&(c<'' || c>''))c=getchar();

    if(c=='-'){f=-;c=getchar();}

    while(c>='' && c<=''){res=res*+c-'';c=getchar();}

    return res*f;

}

struct lnode{

    int data,v,rev;

    bool g;

    lnode *next;

}*a[];

int n,m,k,top=,tail=,ans=;

int d[][],col[]={},c[]={};

int q[];

bool instack[]={};

void spfa(int i){

    int x=q[i];

    lnode *p=a[x];

    while(p){

        if(d[p->data][]>d[x][]+p->v){

            if(instack[p->data]==false){

                instack[p->data]=true;

                d[p->data][]=d[x][]+p->v;

                col[p->data]=col[x];

                q[top++]=p->data;if(top>)top=;

            }else{

                d[p->data][]=d[x][]+p->v;

                col[p->data]=col[x];

            }

        }

        p=p->next;

    }

}

void spfb(int i) {

    int x=q[i];

    lnode *p=a[x];

    while(p) {

        if(d[p->data][]>d[x][]+p->rev) {

            if(instack[p->data]==false) {

                instack[p->data]=true;

                d[p->data][]=d[x][]+p->rev;

                c[p->data]=c[x]; q[top++]=p->data;

                if(top>)top=;

            }else {

                d[p->data][]=d[x][]+p->rev; c[p->data]=c[x];

            }

            if(c[p->data]!=col[p->data])ans=min(ans,d[p->data][]+d[p->data][]);

        } else if(col[p->data]!= && c[x]!=col[p->data])

            ans=min(ans,d[p->data][]+d[x][]+p->rev); p=p->next;

    }

}

int main()

{

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

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

    n=getint();m=getint();

    for(int i=;i<=n;++i)a[i]=NULL,d[i][]=,d[i][]=;

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

        int x=getint(),y=getint(),z1=getint(),z2=getint();;

        lnode *p=new lnode;

        p->data=y;p->v=z1;p->rev=z2;p->next=a[x];a[x]=p;

        p=new lnode;

        p->data=x;p->v=z2;p->rev=z1;p->next=a[y];a[y]=p;

    }

    lnode *p=a[];int now=;

    instack[]=true;d[][]=;

    while(p){

        q[top++]=p->data;col[p->data]=++now;d[p->data][]=p->v;

        instack[p->data]=true;

        p=p->next;

    }

    while(tail!=top){spfa(tail);instack[q[tail]]=false;tail++;if(tail>)tail=;}

    for(int i=;i<=n;++i)instack[i]=false;

    instack[]=true;d[][]=;

    p=a[];top=;tail=;now=;

    while(p){

        q[top++]=p->data;c[p->data]=++now;d[p->data][]=p->rev;

        instack[p->data]=true;

        p=p->next;

    }

    while(tail!=top){spfb(tail);instack[q[tail]]=false;tail++;if(tail>)tail=;}

    cout<<ans;

    return ;

}

洞穴

【POI2004】【Bzoj2069】T2 洞穴 zaw

T2 洞穴zaw

Solution

Code