#P3040. 最短路(road)

最短路(road)

题目描述

n n 个点,m m 条边的有向图,求点 1 1 到点 n n 的最短路(保证存在)。

输入格式

第一行两个整数 n n 、m m ,表示点数和边数。

第二行六个整数 t t 、rxa rxa 、rxc rxc 、rya rya 、ryc ryc 、rp rp 。

前 t t 条边采用如下方式生成:

1.初始化 x=y=z=0 x=y=z=0 。

2.重复以下过程 T T 次:

x=(x×rxa+rxc) mod rp;x=(x\times rxa+rxc)\bmod rp; y=(y×rya+ryc) mod rp;y=(y\times rya+ryc)\bmod rp; a=min⁡(x mod n+1,y mod n+1);a=\min(x\bmod {n+1},y\bmod {n+1}); b=max⁡(x mod n+1,y mod n+1);b=\max(x\bmod {n+1},y\bmod {n+1});

则有一条从 a a 到 b b 的,长度为 108−100a 10^8-100a 的有向边。

后 m−t m-t 条边采用读入方式:

接下来 m−t m-t 行每行三个整数 x,y,z x,y,z ,表示一条从 x x 到 y y 长度为 z z 的有向边。

输出格式

一个整数,表示 1−n 1-n 的最短路。

样例输入

3 3
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1

样例输出

2

提示

请采用高效的堆来优化 Dijkstra 算法。

数据规模与约定

对于 100%100\% 的数据,1≤x,y≤n 1\leq x,y\leq n ,0<z,rxa,rxc,rya,ryc,rp<231 0<z,rxa,rxc,rya,ryc,rp<2^{31} ,1≤n≤1×106 1\leq n\leq 1\times 10^6 ,1≤m≤1×107 1\leq m\leq 1\times 10^7 。

题目来源

WC2013 营员交流-lydrainbowcat