HDU 5361（Dijkstra+并查集）

た入场券 2022-05-28 13:08 126阅读 0赞

# In Touch #

**Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)  
Total Submission(s): 2845    Accepted Submission(s): 754**

Problem Description

There are n soda living in a straight line. soda are numbered by   1,2,…,n from left to right. The distance between two adjacent soda is 1 meter. Every soda has a teleporter. The teleporter of   i\-th soda can teleport to the soda whose distance between   i\-th soda is no less than   li and no larger than   ri. The cost to use   i\-th soda's teleporter is   ci.  
  
The   1\-st soda is their leader and he wants to know the minimum cost needed to reach   i\-th soda   (1≤i≤n).

Input

There are multiple test cases. The first line of input contains an integer   T, indicating the number of test cases. For each test case:  
  
The first line contains an integer   n   (1≤n≤2×105), the number of soda.   
The second line contains   n integers   l1,l2,…,ln. The third line contains   n integers   r1,r2,…,rn. The fourth line contains   n integers   c1,c2,…,cn.   (0≤li≤ri≤n,1≤ci≤109)

Output

For each case, output   n integers where   i\-th integer denotes the minimum cost needed to reach   i\-th soda. If   1\-st soda cannot reach   i\-the soda, you should just output -1.

Sample Input

1 5 2 0 0 0 1 3 1 1 0 5 1 1 1 1 1

Sample Output

0 2 1 1 -1

*Hint*

If you need a larger stack size, please use \#pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

Author

zimpha@zju

Source

[2015 Multi-University Training Contest 6][]

Recommend

wange2014

思路：主要解决边过多的问题，并查集的作用是跳过已更新的点，一个点被更新过一次之后就一定会是最短的，因为dis数组处理的时候要加上该点的cost，目的是为了找出下一次能被更新到最短距离的点。所以一个点一经更新，必定最短，用并查集将已更新的点跳过。

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    const int maxn=2e5+10;
    ll c[maxn], dis[maxn];
    int l[maxn], r[maxn], F[maxn];
    struct node{
    	ll val;
    	int id;
    	
    	bool operator < (const node a) const {
    		return val>a.val;
    	}
    };
    int n;
    
    void init(){
    
    	for(int i=1; i<=n+5; i++)
    	{
    		F[i]=i;
    		dis[i]=INF;
    	}	
    	return;	
    }
    
    int _find(int x){
    	return F[x]==x ? x : F[x]=_find(F[x]);
    }
    
    void conbi(int x, int y){
    	int tx=_find(x), ty=_find(y);
    	
    	if(tx!=ty) F[tx]=ty;
    	return;
    }
    
    void Dijkstra(int s){
    	dis[s]=c[s];
    	priority_queue<node> q;
    	q.push((node){c[s], s});
    	while(!q.empty()){
    		node it=q.top();
    		q.pop();	
    		
    		for(int i=-1; i<=1; i+=2){
    			int L=it.id+l[it.id]*i, R=it.id+r[it.id]*i;
    			if(L>R) swap(L,R);
    			
    			L=max(1, L);
    			R=min(n, R);
    			if(L>R) continue;
    			
    			for(int j=L; j<=R; j++)
    			{
    				j=_find(j);
    				if(j>R) break;
    				
    				if(dis[j]>dis[it.id]+c[j])
    				{
    					dis[j]=dis[it.id]+c[j];
    					q.push((node){dis[j], j});
    				}
    				conbi(j, j+1);
    			}
    		}
    		
    	}
    }
    
    int main()
    {
    	int T;
    	scanf("%d", &T);
    	while(T--){
    		scanf("%d", &n);
    		for(int i=1; i<=n; i++) scanf("%d", &l[i]);
    		for(int i=1; i<=n; i++) scanf("%d", &r[i]);
    		for(int i=1; i<=n; i++) scanf("%lld", &c[i]);
    		
    		init();
    
    		Dijkstra(1);
    		
    		for(int i=1; i<=n; i++)
    		{
    			if(dis[i]==INF)
    				printf("-1%s", i==n? "\n":" ");
    			else
    				printf("%lld%s", dis[i]-c[i], i==n?"\n":" ");
    		}
    	}
        return 0;
    }

[2015 Multi-University Training Contest 6]: http://acm.hdu.edu.cn/search.php?field=problem&key=2015+Multi-University+Training+Contest+6&source=1&searchmode=source