In Touch

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 67 Accepted Submission(s): 11

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

(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++. 
 

Source

求最短路：把一个集合的点看做是一个点，这样就能够用djstra算法做了。然后因为每一个点最多标记一次最短路，用set维护一个点集合。

当最短路找到一个一个集合的时候，把这个集合里还存在的点都取出就可以。取出后。每一个点又能够去两个集合。

再向保存最短路的set里更新集合信息就可以。具体看代码。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 200007#define ll long longint lp[maxn],rp[maxn];ll cosw[maxn];ll dist[maxn];set
          
            haha;struct Node{ int id; ll cost;};bool operator < (Node a,Node b){ if(a.cost == b.cost) return a.id < b.id; return a.cost < b.cost;}set
           
             mind;int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 0;i < n; i++) scanf("%d",&lp[i]); for(int i = 0;i < n; i++) scanf("%d",&rp[i]); for(int i = 0;i < n; i++) scanf("%d",&cosw[i]); haha.clear(); mind.clear(); memset(dist,-1,sizeof(dist)); dist[0] = 0; Node x,y; x.id = 0; x.cost = cosw[0]; mind.insert(x); for(int i = 1;i < n; i++) haha.insert(i); set
            
             ::iterator it,it2; while(mind.size() > 0){ x = *mind.begin(); mind.erase(mind.begin()); it = haha.lower_bound(x.id - rp[x.id]); while(it != haha.end() && *it <= x.id - lp[x.id]){ y.id = *it; y.cost = x.cost + cosw[y.id]; dist[y.id] = x.cost; mind.insert(y); it2 = it++; haha.erase(it2); } it = haha.lower_bound(x.id + lp[x.id]); while(it != haha.end() && *it <= x.id + rp[x.id]){ y.id = *it; y.cost = x.cost + cosw[y.id]; dist[y.id] = x.cost; mind.insert(y); it2 = it++; haha.erase(it2); } } for(int i = 0;i < n; i++){ if(i) printf(" "); printf("%I64d",dist[i]); } printf("\n"); } return 0;}

转载地址：http://moukm.baihongyu.com/

你可能感兴趣的文章