对于一个图，n个节点，有向边，求点s到其他所有点的最短路。
题目给的边的方式：
u -> v
[l,r] -> v
v -> [l,r]
这样的话边数是O(n^2)级别的，怎么做？
假设把[1,n]建成segment tree 后，有tot个节点。
则建一个新图，新图有2 * tot + n个节点
新图多了2 * tot个节点，表示2棵线段树A，B
点的编号分类：
A - [1,tot]
B - [tot + 1,2 * tot]
C - [2 * tot + 1,2 * tot + n]
tree内节点：
A - 表示第1个线段树的点，由父节点向子节点连边，权为0
B - 表示第2个线段树的点，由子节点向父节点连边，权为0
叶节点：
A - 点x向原图对应的点连边，权为0，即x -> 2 * tot + x
B - 原图对应的点向点x连边，权为0，即2 * tot + x -> x + tot
在转换原图的边的时候：
u -> v 在C对应的节点连
v -> [l,r] C连向A中[l,r]对应节点
[l,r] -> v B中[l,r]对应节点连向C
原文：http://www.cnblogs.com/-maybe/p/6637696.html