bzoj3040 最短路＋配对堆优化

3040: 最短路(road)

Time Limit: 60 Sec Memory Limit: 200 MB
Submit: 1859 Solved: 564
[Submit][Status][Discuss]

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算法。

第一眼以为是裸堆优化dijkstra

看到hzwer题解发现要用奇怪的堆优化

据说priority_queue里有五大堆，这里用的是配对堆

 1 #include <stdio.h>
 2 #include <ext/pb_ds/priority_queue.hpp>
 3 #include <string.h>
 4 #define inf 10000000000000000LL
 5 #include <algorithm>
 6 using namespace std;
 7 typedef pair<long long , int > pii;
 8 //priority_queue <pii, vector<pii>, greater<pii > > q;
 9 using namespace __gnu_pbds;
10 typedef __gnu_pbds::priority_queue <pii,  greater<pii >, pairing_heap_tag > heap;
11 heap::point_iterator id[1000005];
12 struct node 
13 {
14     int u, v, w, next;
15 }a[10000005];
16 int tot, n, m, rxa, rxc, rya, ryc;
17 long long dis[1000005];
18 int rp, T, first[1000005];
19 void addedge(int st, int end, int val)
20 {
21     a[++tot].u = st;a[tot].v = end;a[tot].w = val;
22     a[tot].next =first[st];first[st] = tot;
23 }
24 int dij(int S)
25 {
26     heap q;
27     for (int i = 1; i <= n; i++)dis[i] = inf;
28     id[1] = q.push(make_pair(0, 1));
29     dis[1] = 0;
30     while (!q.empty())
31     {
32         int u = q.top().second;q.pop();
33         for (int e = first[u]; e != -1; e = a[e].next)
34         {
35             int v = a[e].v;
36             if (dis[u] + a[e].w < dis[v])
37             {
38                 dis[v] = dis[u] + a[e].w;
39                 if (id[v] != 0)
40                     q.modify(id[v], make_pair(dis[v], v));
41                 else id[v] = q.push(make_pair(dis[v], v));
42             }
43         }
44     }
45 }
46 int main()
47 {
48     scanf("%d %d", &n, &m);
49     scanf("%d %d %d %d %d %d", &T, &rxa, &rxc, &rya, &ryc, &rp);
50     int x , y , z , A, B;
51     x = y = z = 0;
52     memset(first, -1, sizeof(first));
53     for (int i = 1; i <= T; i++)
54     {
55         x = ((long long )x*rxa + rxc) % rp;
56         y = ((long long )y*rya + ryc) % rp;
57         A = min(x%n+1, y%n+1);
58         B = max(y%n+1, y%n+1);
59         addedge(A, B, 100000000 - 100*A);   
60      }
61      for (int i = 1; i <= m - T; i++)
62      {
63         scanf("%d %d %d", &x, &y, &z);
64         addedge(x, y, z);
65      }
66      dij(1);
67      printf("%lld
", dis[n]);
68 }