[JSOI2010] 旅行

2015年3月23日3,9042

给定一张无向图,可以k次交换两条边边权,求1到n的最短路

交换执行于求最短路之前,边权1<=c<=1000
点数<=50
边数<=150
k<=20

此题找不到题解求神犇留言做法

我的想法。。。先求从1-n,无视i条边边权的最短路,然后在路径外找i条最短的加回去。。

最后只对了5个点。。。

 

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
anonymousWuvin Recent comment authors
  Subscribe  
提醒
anonymous
anonymous

一定是选一条路径,将大的边换成小的。但是不能直接取前K小,有可能会交换到已经在路径上的边。
注意到已经在路径上的边加上交换的边一定是排序后边的一个前缀,所以可以枚举这个前缀,然后求出dis[u][i][j]表示从1到u,经过i条已经在前缀的边,替换了j条边,这种情况的最短路(不包含这i+j条边),用dis[N][i][j]+w[1..i+j]更新答案(i+j小于前缀长度时可能会不合法,所以只能用i+j等于前缀长度的更新答案)。
有一个问题是可能存在边权相同的边,排序上可能会有一点问题,我的做法是枚举边权,然后前缀长度就是一个范围。

Wuvin
Wuvin

大神,我为什么在bzoj上找不到这道题?