【題目描述】： 圖圖計劃去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; }

轉載于:https://www.cnblogs.com/ukcxrtjr/p/11556592.html

總結

以上是生活随笔為你收集整理的UOJ #588. 图图的旅行的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。