题目描述
n 个点,m 条边的有向图,求点 1 到点 n 的最短路(保证存在)。
输入格式
第一行两个整数 n、m,表示点数和边数。
第二行六个整数 t、rxa、rxc、rya、ryc、rp。
前 t 条边采用如下方式生成:
1.初始化 x=y=z=0。
2.重复以下过程 T 次:
x=(x×rxa+rxc)modrp;
y=(y×rya+ryc)modrp;
a=min(xmodn+1,ymodn+1);
b=max(ymodn+1,ymodn+1);
则有一条从 a 到 b 的,长度为 108−100a 的有向边。
后 m−t 条边采用读入方式:
接下来 m−t 行每行三个整数 x,y,z,表示一条从 x 到 y 长度为 z 的有向边。
输出格式
一个整数,表示 1−n 的最短路。
样例输入
3 3
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1
样例输出
2
提示
请采用高效的堆来优化 Dijkstra 算法。
数据规模与约定
对于 100% 的数据,1≤x,y≤n,0<z,rxa,rxc,rya,ryc,rp<231,1≤n≤1×106,1≤m≤1×107。
题目来源
WC2013营员交流-lydrainbowcat