对于DFS,随便生成一组N=25的数据乱搞一下即可使DFS TLE
对于不用高精的,来一组(原理显而易见)

25
0 1999 1997 1993 1987 1979 1973 1951 1949 1933 1931 1913 1907 1901 1889 1879 1877 1873 1871 1867 1861 1847 1831 1823 1811
1999 0 1997 1993 1987 1979 1973 1951 1949 1933 1931 1913 1907 1901 1889 1879 1877 1873 1871 1867 1861 1847 1831 1823 1811
1997 1997 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1993 1993 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1987 1987 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1979 1979 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1973 1973 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1951 1951 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1949 1949 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1933 1933 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1931 1931 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1913 1913 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1907 1907 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1901 1901 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1889 1889 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1879 1879 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1877 1877 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1873 1873 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1871 1871 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1867 1867 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1861 1861 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1847 1847 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1831 1831 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1823 1823 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1811 1811 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

答案5502823025424237876165896736743319066044092668746325583050517199826288904116379

数据太弱...
题解
--------------透剧结界------------------

定义:
s-t瓶颈路 => 一条s-t路,其经过的最小边最大.
可以二分解瓶颈路,虽然我不知道有没有更好算法.

求所有路的lcm:
考虑某个素数p.
构造一个新图,该图中的边权是原边权(分解式)中p的次数.
则p在答案中的次数是该新图的s-t瓶颈路的最小边(设为k).
最后把所有p^k乘起来即可.
设[1..最大边权]中素数有P个
W=最大边权
时间O(PElgW)
(参见gcd,lcm在分解素因数下的定义)

• 顺便该算法+高精度P代码 (3642) Hoblovski 2014-03-29 21:33:12