【Travel】

【问题描述】

小YJQ要进行一次旅行。这回他要在需要为1到n的n个城市之间旅行。这n个城市之间共有m条连接两个城市的单行公路,对于第i条公路的风景有一个评分ai。小YJQ有一个要求:

挑选旅行路线时经过某条路时看到的风景比上一条的公路的风景评分更高。小YJQ想看到尽可能多的风景,请你告诉他他能找到的最长的满足他要求的旅行路线有多长。

(每条公路长度视为1,可以重复经过一个城市)

【输入格式】

第一行为两个整数n,m

接下来m行,每行三个证书xi yi ai分别代表每条公路的起点序号,终点序号,风景分数。

【输出格式】

输出一个整数,为满足要求的最长路线的长度。

【输入样例】

3 3

1 2 1

2 3 2

3 1 3

【输出样例】

3

【样例说明】

最长路径为1->2->3->1

【数据范围】

对于100%的数据,n,m≤300000,1≤ai≤100000;

对每条边排个序,然后对每条边扫描跟它接在一起的边,看比它小的边能不能更新它的值,更新即可。

贴一发有缺陷但是能AC的代码:

一发应该是没有问题的代码:(琦爷真是太神了OrzOrz)

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

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

留下你的评论

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

*