注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3040]最短路(road)  

2015-01-29 11:11:55|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3040: 最短路(road)

Time Limit: 60 Sec  Memory Limit: 200 MB
Submit: 1749  Solved: 523
[Submit][Status]

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

2

HINT

【注释】
请采用高效的堆来优化Dijkstra算法。

Solution

在hint里面。。。

开始一直过不去,要了数据,惊讶的发现只要把后面M-T条边拿去跑dij就可以过了。。。

Code

/**************************************************************
    Problem: 3040
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1812 ms
    Memory:196156 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
inline int getc(){
    static char buf[1<<15],*S=buf,*T=buf;
    if(S==T)if(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)return 0;
    return*S++;
}
int aa,bb,ch;inline int F(){
    while(ch=getc(),(ch<48||ch>57)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch^48,bb=1);
    while(ch=getc()^48,ch>=0&&ch<=9)aa=(aa<<3)+(aa<<1)+ch;return bb?aa:-aa;
}
typedef long long ll;
const int MAXN=1000010,MAXM=10000010;
int la[MAXN],et,in[MAXN],hr;ll d[MAXN];
struct E{int to;ll v;int nxt;}e[MAXM];
#define add(x,y,v) (e[++et]=(E){y,v,la[x]},la[x]=et)
struct H{int n;ll d;}h[MAXN<<1];
void ins(const H&t){int i;for(i=++hr;i!=1&&t.d<h[i>>1].d;i>>=1)h[i]=h[i>>1];h[i]=t;}
void dlt(){hr--;int i;
    for(i=1;(i<<1)<=hr&&!(h[hr+1].d<=h[i<<1].d&&h[hr+1].d<=h[i<<1|1].d);)
    i<<1!=hr&&h[i<<1|1].d<h[i<<1].d?(h[i]=h[i<<1|1],i=i<<1|1):(h[i]=h[i<<1],i=i<<1);
    h[i]=h[hr+1];
}
void dijkstra(int s){
    memset(d,127,sizeof(d));
    memset(in,0,sizeof(in));int i;ll tmp;
    for(ins((H){s,d[s]=0});hr;dlt())if(!in[h[1].n]){
        for(in[h[1].n]=1,i=la[h[1].n];i;i=e[i].nxt)
        if(d[e[i].to]>(tmp=d[h[1].n]+e[i].v))
        ins((H){e[i].to,d[e[i].to]=tmp});
    }
}
int n,m,x,y,z;
int main(){
    for(n=F(),m=F()-F(),F(),F(),F(),F(),F();m--;)x=F(),y=F(),z=F(),add(x,y,z);
    dijkstra(1),printf("%lld\n",d[n]);
}
  评论这张
 
阅读(30)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018