【bzoj2407】探险

2014年11月27日1,7751

Description

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

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

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

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

Input

第一行两个数n,m表示溶洞的数量以及暗道的数量。

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

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

题解

看到网上的做法是枚举出去的第一条边,然后走最短路回来(不经过出去的边)

但是这不是暴力么。。。

事实上这题。。。

注意到当我们走出第一步后,题目便转换为求最短路,而在计算每个点返回原点时存在大量的重复计算。

先求出从原点出发到达每个点的最短距离d[i], 记录该路径从原点出发到达的第一个点p[i]

创建虚拟汇点T,构建新图

 

依次枚举原图所有边

1: 该边为(u,1,w) ,即从u点连向原点的边

若 u != p[u] 说明从原点到达点u的最短路径中没有经过边(1,u),

即边(u,1)可以被使用,此时存在一条原点S -> p[u] -> … -> u -> S 的路径

在新图中直接创建一条 (S,T, d[u]+w)的边

若u == p[u] 说明到达点u的最短路径是由边(1,u)得到,所以不能通过d[u]+w的方式返回原点。 但如果存在其他方式到达点u,则可以通过该边返回,故在新图中创建边(u,T,w)

 

2: 该边为(1,v,w) 即该边为从原点出发的边

若p[v]=v,即说明原点到达点v的最短路径即为(1,v,w),故此时不再添加边

若p[v]!=v,说明原点到达点v的最短路径不是(1,v,w),此时需要在新图中添加边(1,v,w)

 

3: 该边为(u,v,w)   (u != 1 && v != 1)

若p[u] != p[v],说明从原点到达点u的最短路径,与从原点到达点v的最短路径不同,即存在S -> p[u] -> u -> v 的路径,创建边(1,v,d[u]+w)

若p[u] == p[v],则在新图中保留原边 (u,v,w)

 

然后在新图中求一次从S到T的最短路

ans = d[T]

 

  • Thief2016年5月24日 下午10:35 回复

    黄学长,我认为您这样做可能是有些萎的:由于题目里注明“可能有多条道路连接两个洞”,所以您记前驱点并不能代表这条路径。诚如这组数据:
    2 2
    1 2 1 1
    1 2 1 1
    理应输出2,但您的程序输出无解
    个人认为记边的话就可以?期待您的答复

    #1