「JoyOI1577」泥泞的道路

2014年7月26日3,9820

描述 Description

公园中有n个景点,编号1~n,并由m条双向道路相连。由于昨天下雨,导致公园中的马路泥泞不堪,每条道路都有一个泥泞程度w。现有Q个游客依次向你求助,想从景点X走到景点Y,他希望找到一条道路,使得经过道路泥泞程度的最大值尽量小。你能设计一个在线算法,帮他们找到方案吗?

输入格式 InputFormat

第一行两个正整数n和m,表示景点数和道路数。
随后m行每行三个正整数x、y、w,用来描述一条道路,它连接x和y景点并且泥泞程度为w。
随后Q行,每行四个参数p1、p2、q1、q2,含义如下:
设数列Si表示你求得的第i个询问的结果(s0=1),则对于第i个询问:
X=(Si-1+p1)*p2 mod n + 1;
Y=(si-1+q1)*q2 mod n + 1;

输出格式 OutputFormat

请对于每个询问,输出结果,即Si。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

对于30%的数据,n<=1000,m<=3000,Q<=1000;
对于100%的数据,n<=100000,m<=300000,Q<=100000;
对于100%的数据,0<=p1、p2、q1、q2<n,w<300000。

题解
知道为什么这题通过率低么!!!
n绝对不止10W,然后si-1的(i-1)是下标,而且这里会爆int!
据说递归还会爆栈
我整个人都跪烂了
其实说白了就是NOIP货车运输T T

 

avatar
  Subscribe  
提醒