【bzoj1576】[Usaco2009 Jan]安全路经Travel

2014年8月7日3,5311

Description

Input

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输入解释:
跟题中例子相同

Sample Output

3
3
6
输出解释:
跟题中例子相同

题解

首先用dijkstra得出最短路径树

然后

我的做法是树链剖分+线段树

对于一条不在最短路树的有向边(无向可看成两条有向)u-v,长度L,设t=lca(u,v)

那么对于t-v的路径上所有点x,都可通过1-t-u-v-x

路径长度为d[u]+L+d[v]-d[x]

最小化这个长度,也就是最小化d[u]+d[v]+L

所以我们可以用这个值去更新t-v所有点(不包括t)的最短路长度

这一步可以用线段树操作。。。

 

  • Chenyao2014年11月5日 上午11:51 回复

    太神了,Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

    #1