「BZOJ3040」最短路(road)
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算法。
题解
请使用高等的stl堆水过此题
曾经，我不会手打堆，于是ndsf说：我们只要会stl就行了
实验证明T T，配对堆的常数非常小，此题stl的配对堆比斐波那契堆更快
26s : 20s
|
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<cstring> #include<ext/pb_ds/priority_queue.hpp> #define ll long long #define pa pair<ll,int> #define llinf 9000000000000000000LL using namespace std; using namespace __gnu_pbds; typedef __gnu_pbds::priority_queue<pa,greater<pa>,pairing_heap_tag > heap; int n,m,cnt,last[1000005]; int T,rxa,rxc,rya,ryc,rp; heap::point_iterator id[1000005]; int x,y,z; ll dis[1000005]; struct data{int to,next,v;}e[10000005]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; } void dijkstra() { heap q; for(int i=1;i<=n;i++)dis[i]=llinf; dis[1]=0;id[1]=q.push(make_pair(0,1)); while(!q.empty()) { int now=q.top().second;q.pop(); for(int i=last[now];i;i=e[i].next) if(e[i].v+dis[now]<dis[e[i].to]) { dis[e[i].to]=e[i].v+dis[now]; if(id[e[i].to]!=0) q.modify(id[e[i].to],make_pair(dis[e[i].to],e[i].to)); else id[e[i].to]=q.push(make_pair(dis[e[i].to],e[i].to)); } } } int main() { n=read();m=read(); T=read();rxa=read();rxc=read();rya=read();ryc=read();rp=read(); int a,b; for(int i=1;i<=T;i++) { x=((ll)x*rxa+rxc)%rp; y=((ll)y*rya+ryc)%rp; a=min(x%n+1,y%n+1); b=max(y%n+1,y%n+1); insert(a,b,100000000-100*a); } for(int i=1;i<=m-T;i++) { x=read(),y=read(),z=read(); insert(x,y,z); } dijkstra(); printf("%lld",dis[n]); return 0; } |
计数器 9675358
OI 课件=>
OI 课件=>
真是平板电视依赖症