bzoj 2259: [Oibh]新型计算机 最短路 建模

bzoj 2259: [Oibh]新型计算机 最短路 建模

Code: #include #include #include #include using namespace std; #define maxn 3000005 int head[maxn], to[maxn], nex[maxn], val[maxn],edges,s,t,pre[maxn],nxt[maxn]; struct Node{ int dist,u; Node(int dist=0,int u=0):dist(dist),u(u){} bool operator <(Node a) const{ return a.distQ; void addedge(int u,int v,int c){ nex[++edges]=head[u],head[u]=edges,to[edges]=v,val[edges]=c; } int d[maxn]; bool done[maxn]; void dijkstra(){ memset(d,0x3f,sizeof(d)); d[s]=0; Q.push(Node(0,s)); while(!Q.empty()){ int u=Q.top().u; Q.pop(); if(done[u]) continue; if(u==t) break; done[u]=true; for(int v=head[u];v;v=nex[v]) if(d[u]+val[v] < d[to[v]]){ d[to[v]]=d[u]+val[v]; Q.push(Node(d[to[v]],to[v])); } } } int main(){ //freopen("input.in","r",stdin); int n,a; scanf("%d",&n); s=1, t=n+1; for(int i=1;i<=n;++i){ scanf("%d",&a); for(int j=i+1;j<=min(n+1,a+i+1)&&!pre[j];++j) addedge(j,j-1,1), pre[j]=1; for(int j=i+a+1;j<=n&&!nxt[j];++j) addedge(j,j+1,1),nxt[j]=1; if(i+a<=n) addedge(i,i+a+1,0); else addedge(i,n+1,i+a-n); } dijkstra(); printf("%d",d[t]); return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。