【Proof】

【问题描述】

给出n条线段,每条线段有两个端点li和ri,选择这条线段需要花费costi,求连接区间[1,R]需要的最小花费。

【输入描述】

输入文件的第一行的两个整数R和n。

接下来n行,每行三个整数li,ri和costi,意义和问题描述一样。

【输出格式】

输出一个整数,表示最小花费。

如果不能覆盖全区间,输出-1.

【输入样例1】

9 3

1 3 101010

4 6 98889

7 9 76543

【输出样例】

-1

【输出说明】

就算选所有的线段,也无法把3—4和6—7连接起来

【输入样例2】

9 7

1 5 3

3 6 8

5 8 4

4 7 6

2 3 7

7 9 2

6 7 5

【输出样例2】

9

【输出样例2说明】

选1 3 6三条线段即可连接全部区间,花费为9

【数据范围】

R≤1000000000 n≤100000 costi≤1000000000

一道有趣的图论题。

首先将所有的线段端点离散化到N以内,对2~N每一条线段都从i向i-1连一条权值为0的边,表示区间[i-1,i]在一条线段中,然后对每条线段从li到ri连一条权值为costi的边,然后从1号点开始跑,这个算法显然是正确的,比如两条线段1,3和2,4从1号点跑到了3号点发现无路可走就跑回到2号点(选了这条线段那么这区间内的点都能到达,所以连权值为0的边)2号点发现可以跑到4号点就继续跑,要求覆盖[1,4]的话就是求从1开始,4结束的最短路。同理求[1,R]即是从1开始到点R的最短路。

另外,最短路要用Dijkstra+heap不要用SPFA,SPFA会被卡的很惨……

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*