UOJ #588. 图图的旅行

【题目描述】：
图图计划去Bzeroth 的精灵王国去旅游，精灵王国由n 座城市组成，第i 座城市有3 个属性x[i]，w[i]，t[i]。在精灵王国的城市之间穿行只能依靠传送阵，第i 座城市的传送阵可以将图图从城市i 传送到距离城市i 不超过w[i]的任意一个城市，并需要t[i]的时间完成传送。现在图图知道了每个城市的坐标x[i]，想知道他从城市s 到城市t 的最小时间。这么难的问题图图当然不会做了，他想让你帮帮他，你能解决这个问题吗？【输入描述】：
第一行包含3 个正整数n、s、t，表示城市个数，起点城市和终点城市。第二行包含n 个整数x[i]，表示第i 座城市的坐标。第三行包含n 个整数w[i]，表示第i 座城市的传送距离。第四行包含n 个整数t[i]，表示第i 座城市的传送时间。【输出描述】：
请输出从城市s 到城市t 的最小时间，保证至少存在一组合法解。【样例输入】：
7 3 7
-1 0 1 2 3 5 10
11 0 1 1 4 10 2
3 1 1 1 2 4 5
【样例输出】：
7
【样例说明】：
路线为3 → 4 → 5 → 1 → 7，时间之和为7。【时间限制、数据范围及描述】：
时间：1s 空间：256M对于30%的数据，1≤n≤2501，所有的t[i]均相等。对于60%的数据，1≤n≤2501。对于100%的数据，1≤n≤152501，0≤w[i],t[i],|x[i]|≤10^9，保证x[i]严格递增。本题的关键是要看出每个点所能到达的点是一个区间,所以直接用线段树的思想来建边,每次只要将一个点连上它所对应的区间即可.
然后线段树内部就父亲连向儿子,这样点数虽增多了,但是边数却减少为nlogn,最后再跑一边dijkstra就行了.Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=1000005;
int n,cnt,head[N*4],X[N],D[N],T[N],wl[N],wr[N];
long long dis[N*4];
bool vis[N*4];
struct Node{int v,nxt,w;
}edge[N*8];
struct node{int u;long long d;
};
bool operator<(const node &p,const node &q){return p.d>q.d;
}
priority_queue<node> q;
void add(int u,int v,int w){cnt++;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt;
}
void build(int o,int l,int r){if (l==r){add(o+n,l,0);return;}int mid=(l+r)>>1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);add(o+n,(o<<1)+n,0);add(o+n,(o<<1|1)+n,0);
}
void update(int o,int l,int r,int u,int ql,int qr,int w){if (l>=ql && r<=qr){add(u,o+n,w);return;}int mid=(l+r)>>1;if (ql<=mid){update(o<<1,l,mid,u,ql,qr,w);}if (qr>=mid+1){update(o<<1|1,mid+1,r,u,ql,qr,w);}
}
void dijkstra(int s){for(int i=1;i<N*4;i++){dis[i]=1e18;}dis[s]=0;q.push((node){s,0});while (!q.empty()){int u=q.top().u;q.pop();if (vis[u]){continue;}vis[u]=1;for (int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if (dis[v]>dis[u]+edge[i].w){dis[v]=dis[u]+edge[i].w;if (!vis[v]){q.push((node){v,dis[v]});}}}}
}
int main(){int s,t;scanf("%d%d%d",&n,&s,&t);for(int i=1;i<=n;i++){scanf("%d",&X[i]);}for(int i=1;i<=n;i++){scanf("%d",&D[i]);}for(int i=1;i<=n;i++){scanf("%d",&T[i]);}build(1,1,n);for (int i=1;i<=n;i++){wl[i]=lower_bound(X+1,X+1+n,X[i]-D[i])-X;wr[i]=upper_bound(X+1,X+1+n,X[i]+D[i])-X-1;}for (int i=1;i<=n;i++){update(1,1,n,i,wl[i],wr[i],T[i]);}dijkstra(s);printf("%lld\n",dis[t]);return 0;
}