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
0 1 2 3 5 7
1 2 1
1 3 3
2 3 1
Sample Output
2
HINT
【注释】
请采用高效的堆来优化Dijkstra算法。
Source
WC2013营员交流-lydrainbowcat
这题内存卡得很紧，要用到STL中的配对堆。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<queue> #include<ext/pb_ds/priority_queue.hpp> #define ll long long using namespace std; using namespace __gnu_pbds; const int N=1000010,M=10000010; int n,m,tot,Next[M],head[N],tree[M]; ll val[M],dis[N]; typedef __gnu_pbds::priority_queue<pair<ll,int>,greater<pair<ll,int> >,pairing_heap_tag> heap; heap::point_iterator id[1000010]; heap Q; void add(int x,int y,long long z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } ll dijstra(int S,int T) { for (int i=1;i<=n;i++) dis[i]=1LL<<50; dis[S]=0;id[S]=Q.push(make_pair(0,S)); while (!Q.empty()) { int u=Q.top().second; Q.pop(); for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (dis[v]>dis[u]+val[i]) { dis[v]=dis[u]+val[i]; if (id[v]!=0) Q.modify(id[v],make_pair(dis[v],v)); else id[v]=Q.push(make_pair(dis[v],v)); } } } return dis[T]; } int main() { scanf("%d%d",&n,&m); int T; ll rxa,rxc,rya,ryc,rp; scanf("%d%lld%lld%lld%lld%lld",&T,&rxa,&rxc,&rya,&ryc,&rp); tot=0; ll x=0,y=0,a,b; for (int 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); add(a,b,1e8-100*a); } for (int i=1;i<=m-T;i++) { int x,y;ll z; scanf("%d%d%lld",&x,&y,&z); add(x,y,z); } printf("%lld\n",dijstra(1,n)); return 0; } |
