bzoj2407 探险 （重构图 + 最短路）

2407: 探险

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 148  Solved: 84
[Submit][Status][Discuss]

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，表示最少所需要的时间。

 

 

（直接抄dalao的题解了orz）

先跑一遍最短路，令$1$到$i$的最短路为$dis[i]$，并记录$1$到$i$的最短路上第一个经过的点$pre[i]$，若$pre[i]==1$则令$pre[i]=i$；

重新构图，对于原图中的一条边$(u,v,w)$：

　　若$u==1$：

　　　　若$pre[v]==v$，忽略此边；否则连边$(S,v,w)$；

　　若$v==1$：

　　　　若$pre[u]==u$，连边$(u,T,w)$；否则连边$(S,T,dis[u]+w)$；

　　若$u!=1$且$v!=1$：

　　　　若$pre[u]==pre[v]$，连边$(u,v,w)$；否则连边$(S,v,dis[u]+w)$；

新图中跑一边$S$到$T$最短路即可；

这样构造把$S->i$的边拆开，就不会导致一条路走两遍；

AC GET☆DAZE

 

↓代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct edge
{
    int to,next,val;
}fet[400039],ret[400039];
int n,fhd[40039],shd[40039],tot,rot,dis[40039],fir[40039],S,T,stp=0x3f3f3f3f;
bool inq[40039],Sinogi[40039];
void add(int u,int v,int ws,int wr)
{
    fet[++tot].to=v,fet[tot].next=fhd[u],fet[tot].val=ws,fhd[u]=tot;
    fet[++tot].to=u,fet[tot].next=fhd[v],fet[tot].val=wr,fhd[v]=tot;
}
void add(int u,int v,int w)
{
    ret[++rot].to=v,ret[rot].next=shd[u],ret[rot].val=w,shd[u]=rot;
}
void spfa(edge net[],int head[])
{
    memset(dis,63,sizeof(dis));
    queue<int>que;
    que.push(S),dis[S]=0,inq[S]=1,fir[S]=S;
    int a,b;
    while(!que.empty())
    {
        a=que.front(),que.pop();
        for(b=head[a];b!=-1;b=net[b].next)
        {
            if(dis[net[b].to]>dis[a]+net[b].val)
            {
                dis[net[b].to]=dis[a]+net[b].val;
                fir[net[b].to]=(fir[a]==S ? net[b].to : fir[a]);
                if(!inq[net[b].to])
                {
                    que.push(net[b].to);
                    inq[net[b].to]=1;
                }
            }
        }
        inq[a]=0;
    }
}
void rebuild(edge net[],int head[])
{
    int a,b;
    for(a=1;a<=n;a++)
    {
        for(b=head[a];b!=-1;b=net[b].next)
        {
            if(a==S)
            {
                if(fir[net[b].to]!=net[b].to)
                {
                    add(1,net[b].to,net[b].val);
                }
            }
            else if(net[b].to==S)
            {
                if(fir[a]!=a)
                {
                    add(S,T,dis[a]+net[b].val);
                }
                else
                {
                    add(a,T,net[b].val);
                }
            }
            else
            {
                if(fir[a]!=fir[net[b].to])
                {
                    add(S,net[b].to,dis[a]+net[b].val);
                }
                else
                {
                    add(a,net[b].to,net[b].val);
                }
            }
        }
    }
}
int main()
{
    memset(fhd,-1,sizeof(fhd));
    memset(shd,-1,sizeof(shd));
    int m,ans=0x3f3f3f3f,a,b,c,d,e;
    scanf("%d%d",&n,&m);
    for(a=1;a<=m;a++)
    {
        scanf("%d%d%d%d",&b,&c,&d,&e);
        if(b==1)
        {
            Sinogi[c]=1,dis[c]=d;
        }
        if(c==1 && Sinogi[b])
        {
            stp=min(stp,d+dis[b]);
        }
        add(b,c,d,e);
    }
    S=1;
    spfa(fet,fhd);
    T=n+1;
    rebuild(fet,fhd);
    spfa(ret,shd);
    printf("%d",min(stp,dis[T]));
    return 0;
}