bzoj 3040: 最短路(road)（堆优化dijkstra）-白红宇

bzoj 3040: 最短路(road)（堆优化dijkstra）

阅读量：2143 次

发布时间：2019-04-30

本文共 1581 字，大约阅读时间需要 5 分钟。

Time Limit: 60 Sec

Memory Limit: 200 MB

Submit: 2811

Solved: 933

[ ][ ][ ]

Description

N个点，M条边的有向图，求点1到点N的最短路（保证存在）。

1<=N<=1000000，1<=M<=10000000

Input

第一行两个整数N、M，表示点数和边数。

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

前T条边采用如下方式生成：

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

2.重复以下过程T次：

x=(x*rxa+rxc)%rp;

y=(y*rya+ryc)%rp;

a=min(x%n+1,y%n+1);

b=max(y%n+1,y%n+1);

则有一条从a到b的，长度为1e8-100*a的有向边。

后M-T条边采用读入方式：

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

1<=x,y<=N，0<z,rxa,rxc,rya,ryc,rp<2^31

Output

一个整数，表示1~N的最短路。

Sample Input

3 3

0 1 2 3 5 7

1 2 1

1 3 3

2 3 1

Sample Output

堆优化dijkstra模板题，不过很卡内存

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define LL long longLL bet[1000005], len[10000005];int cnt, node[10000005], nxt[10000005], head[1000005];void Add(int x, int y, LL z){	node[++cnt] = y;	nxt[cnt] = head[x];	head[x] = cnt;	len[cnt] = z;}void Dij(){	int i, v, now;	memset(bet, 10, sizeof(bet));	bet[1] = 0;	priority_queue
       
        
          > q; q.push(make_pair(0, 1)); while(1) { while(q.empty()==0 && -bet[q.top().second]
         
          bet[now]+len[i]) { bet[v] = bet[now]+len[i]; q.push(make_pair(-bet[v], v)); } } }}int main(void){ int i, n, m; LL T, rxa, rxc, rya, ryc, rp, x, y, z, a, b, l; cnt = x = y = z = 0; scanf("%d%d", &n, &m); scanf("%lld%lld%lld%lld%lld%lld", &T, &rxa, &rxc, &rya, &ryc, &rp); for(i=1;i<=T;i++) { x = (x*rxa+rxc)%rp; y = (y*rya+ryc)%rp; a = min(x%n+1, y%n+1); b = max(y%n+1, y%n+1); l = (LL)1e8-100*a; Add(a, b, l); } memset(head, 0, sizeof(head)); for(i=T+1;i<=m;i++) { scanf("%lld%lld%lld", &x, &y, &z); Add(x, y, z); } Dij(); printf("%lld\n", bet[n]); return 0;}