【题目描述】：图图计划去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 1011 0 1 1 4 10 23 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;}