*bzoj 3040 最短路 (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

Output

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

Sample Input

Sample Output

HINT

【注释】

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

Source

WC2013营员交流-lydrainbowcat

【分析】完全是dijkstra的堆优化！然而这内存卡的太紧了。一下是悲惨的刷题经历。

【NUM.1——系统堆】（上交后改成lld)

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        //#include
       
         //#include
        
          using namespace std; typedef long long ll; typedef pair
         
          Pair; const int N=1000005; const int M=10000005; ll x,y,z,rxa,rxc,rp,rya,ryc,aa,bb,dis[N],cnt; struct arr{int next,go,s;}a[M]; int xx,yy,t,i,now,n,m,end[N],go; bool flag[N]; priority_queue< Pair,vector
          
           ,greater
           
             >q; void make_up(int u,int v,int w) { a[++cnt].go=v;a[cnt].s=w;a[cnt].next=end[u];end[u]=cnt; } int main() { scanf(%d%d,&n,&m); scanf(%d%I64d%I64d%I64d%I64d%I64d,&t,&rxa,&rxc,&rya,&ryc,&rp); x=y=z=0; for (i=1;i<=t;i++) { x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp; aa=min(x%n+1,y%n+1);bb=max(y%n+1,y%n+1); make_up((int)aa,(int)bb,100000000-100*aa); } for (i=1;i<=m-t;i++) { scanf(%d%d%d,&xx,&yy,&z); make_up(xx,yy,z); } memset(dis,60,sizeof(dis));dis[1]=0; q.push(pair
            
             (dis[1],1)); while (!q.empty()) { Pair temp=q.top();q.pop(); now=temp.second; flag[now]=true; for (i=end[now];i;i=a[i].next) { go=a[i].go; if (dis[go]>dis[now]+ll(a[i].s)&&!flag[go]) { dis[go]=dis[now]+ll(a[i].s);q.push(make_pair(dis[go],go)); } } } printf(%I64d,dis[n]); return 0; }
            
           
          
         
        
       
      
     
    
   
  

【NUM2——手工堆】

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; typedef long long ll; typedef pair
      
       Pair; const int N=1000005; const int M=10000005; ll x,y,rxa,rxc,rp,rya,ryc,aa,bb,dis[N],go,cnt,pre[N],end[N]; Pair d[N*2];char ch; struct arr{int next,go,s;}a[M]; bool flag[N]; int xx,yy,z,t,i,now,n,m,len; void make_up(int u,int v,int w) { a[++cnt].go=v;a[cnt].s=w;a[cnt].next=end[u];end[u]=cnt; } void swap(Pair &a,Pair &b) { Pair c=a;a=b;b=c; } void pop() { pre[d[1].second]=0;pre[d[len].second]=1;d[1]=d[len];len--; int now=1; while (true) { ll t1=d[now].first,t2=d[now*2].first,t3=d[now*2+1].first; if (t2
       
        1) { pre[p]=now/2;pre[d[now/2].second]=now; swap(d[now],d[now/2]);now/=2; } } void push(Pair that) { d[++len]=that;int now=len,p=that.second;pre[p]=len; up(now,p); } int Read() { while (ch<'0'||ch>'9') ch=getchar(); int s=0; while (ch>='0'&&ch<='9') s=s*10+ch-48,ch=getchar(); return s; } int main() { scanf(%d%d,&n,&m); scanf(%d %lld %lld %lld %lld %lld,&t,&rxa,&rxc,&rya,&ryc,&rp); x=y=z=0; for (i=1;i<=t;i++) { x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp; aa=min((ll)x%n+1,(ll)y%n+1);bb=max(ll(y%n+1),ll(y%n+1)); make_up((int)aa,(int)bb,(int)100000000-100*aa); } ch='!'; for (i=1;i<=m-t;i++) { xx=Read();yy=Read();z=Read(); make_up(xx,yy,z); } memset(dis,60,sizeof(dis)); memset(pre,0,sizeof(pre)); dis[1]=0;push(make_pair(dis[1],1));len=1;pre[1]=1; while (len) { Pair temp=d[1];pop(); now=temp.second;flag[now]=true; for (i=end[now];i;i=a[i].next) { go=a[i].go; if (dis[go]>dis[now]+ll(a[i].s)&&!flag[go]) { dis[go]=dis[now]+ll(a[i].s); if (pre[go]==0) push(make_pair(dis[go],go)); else { d[pre[go]].first=dis[go]; up(go,d[pre[go]].second); } } } } printf(%lld,dis[n]); return 0; }
       
      
     
    
   
  

【结果】听说SYC大神A过去了。仔细看他的代码，和我的NUM.1有点类似啊~~仔细一看，原来他打错了一个字母。一共有T条边生成，但他只生成了N条边！！于是我把t也改成了n，就过去了~~~~

【正解】当然那是卡数据的行为啊！！据说要用斐波那契堆或是系统配对堆。那么以后来研究~~