【刷题】BZOJ 2407 探险

Description

探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！

比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。

如果就这么点限制，那么问题就太简单了，可是举办方又提出了一个条件：不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢？

到了大溶洞口后，小T愉悦地发现这个地方他曾经来过，他还记得有哪些暗道，以及通过每条暗道的时间。小T现在向你求助，你能帮他算出至少要多少时间才能回到大溶洞吗？

Input

第一行两个数_n__，m_表示溶洞的数量以及暗道的数量。

接下来m行，每行4个数_s_、t、w、v，表示一个暗道连接的两个溶洞_s_、t，这条暗道正着走（s à t）的所需要的时间_w_，倒着走（t à s）所需要的时间_v_。由于溶洞的相对位置不同，_w_与_v_可能不同。

Output

输出一行一个数t，表示最少所需要的时间。

Sample Input

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

Sample Output

8

HINT

N<=10000,M<=200000,1<=W,V<=10000

Solution

同【刷题】BZOJ 2069 [POI2004]ZAW

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define ft first
#define sd second
#define pb(a) push_back(a)
#define mp(a,b) std::make_pair(a,b)
#define ITR(a,b) for(auto a:b)
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=10000+10,MAXM=200000+10,inf=0x3f3f3f3f;
int n,m,e,beg[MAXN],nex[MAXM<<1],to[MAXM<<1],was[MAXM<<1],d[MAXN],dir[MAXN],ans=inf;
std::priority_queue< std::pair<int,int>,std::vector< std::pair<int,int> >,std::greater< std::pair<int,int> > > q;
namespace IO{
    const int Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;
    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}
    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch-'0');
        x*=f;
    }
    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static int sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y,int z)
{
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
    was[e]=z;
}
inline void Dijstra(int s)
{
    memset(d,inf,sizeof(d));
    d[s]=0;
    q.push(mp(d[s],s));
    while(!q.empty())
    {
        std::pair<int,int> pr=q.top();
        q.pop();
        if(pr.ft!=d[pr.sd])continue;
        int x=pr.sd;
        for(register int i=beg[x];i;i=nex[i])
            if(to[i]==1)
            {
                if(dir[x])continue;
                if(d[n+1]>d[x]+was[i])d[n+1]=d[x]+was[i];
            }
            else
            {
                if(x==1&&!dir[to[i]])continue;
                if(d[to[i]]>d[x]+was[i])d[to[i]]=d[x]+was[i],q.push(mp(d[to[i]],to[i]));
            }
    }
}
inline void solve(int ps)
{
    for(register int i=beg[1];i;i=nex[i])dir[to[i]]=(to[i]>>ps)&1;
    Dijstra(1);
    chkmin(ans,d[n+1]);
    for(register int i=beg[1];i;i=nex[i])dir[to[i]]^=1;
    Dijstra(1);
    chkmin(ans,d[n+1]);
}
int main()
{
    read(n);read(m);
    REP(i,1,m)
    {
        int u,v,w1,w2;read(u);read(v);read(w1);read(w2);
        insert(u,v,w1);insert(v,u,w2);
    }
    REP(i,0,13)solve(i);
    write(ans,'\n');flush();
    return 0;
}

【刷题】BZOJ 2407 探险

原文：https://www.cnblogs.com/hongyj/p/10088236.html