bzoj#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)modrp;x=(x\times rxa+rxc)\bmod rp; y=(y×rya+ryc)modrp;y=(y\times rya+ryc)\bmod rp; a=min(xmodn+1,ymodn+1);a=\min(x\bmod {n+1},y\bmod {n+1}); b=max(ymodn+1,ymodn+1);b=\max(y\bmod {n+1},y\bmod {n+1});

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

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

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

输出格式

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

样例输入

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

样例输出

2

提示

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

数据规模与约定

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

题目来源

WC2013营员交流-lydrainbowcat