【bzoj3694】【FJ2014集训】最短路

2014年7月20日2,3590

题目描述

给出一个n个点m条边的无向图,n个点的编号从1~n,定义源点为1。定义最短路树如下:从源点1经过边集T到任意一点i有且仅有一条路径,且这条路径是整个图1i的最短路径,边集T构成最短路树。

给出最短路树,求对于除了源点1外的每个点i,求最短路,要求不经过给出的最短路树上的1i的路径的最后一条边。

输入格式

第一行包含两个数nm,表示图中有n个点和m条边。

接下来m行,每行有四个数aibiliti,表示图中第i条边连接aibi权值为liti1表示这条边是最短路树上的边,ti0表示不是最短路树上的边。

输出格式

输出n-1个数,第i个数表示从1i+1的要求的最短路。无法到达输出-1

样例输入

5 9

3 1 3 1

1 4 2 1

2 1 6 0

2 3 4 0

5 2 3 0

3 2 2 1

5 3 1 1

3 5 2 0

4 5 4 0

样例输出

6 7 8 5

数据规模

对于30%的数据,n100m2000

对于100%的数据,n4000m1000001li100000

题解

这题是usacp安全路径简化版。。。

而且由于数据是随机的,树的深度是logn T T

所以暴力都能过。。。

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

对于一条不在最短路树的有向边(无向可看成两条有向)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)的最短路长度

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