Ski Resorts
题目简述：
给定一个已知连接关系的图，图中的点标号0 ~ n-1，每个点有一个特征值。如果i,j之间有边，并且i 的特征不小于 j的。那么就可以从i 到 j。现在要修改这些特征值，使得可以从0经过若干条边到达n-1, 修改的代价定义为所有点的原始特征值与修改后的特征值的绝对值之和，现在要最小化这个代价。
思路
从0到n-1的代价最小，这跟我们以前熟悉的最短路很相似。我们尝试对问题进行转化。
算法
重新建图， 定义每个点为(i, j), 表示第i个点修改到原来第j个点的特征值。根据题目的约束建边，假设(i, j)到（k, l)有边，那么这条边的权值为 |l的特征值 - k的特征值|，即这条边出点的修改代价。然后我们新增一个点S向（0, 0~n-1）连边，权值类似定义， 再新增一个点T 从（n-1, 0~n-1）向其连边，权值为0.题目的答案即为S 到 T的最短路。
注意
题目的内存有限制，我选择不显示建边，用的Dijkstra。
吐槽
乍一眼我看错题，我先以为是要求0能到达其它所有点。我想了良久，没有答案。如果有哪位大神解决这个加强版的问题请不吝赐教。