HDU 5361 In Touch

Problem Description

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

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

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

Hint

If you need a larger stack size,

please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

這題的難點主要在于邊的條數過多，不能像普通的最短路那樣子跑。

不過此題的特點在于對于每個點來說，從這個點出去能到的任何點這個過程的花費是相同的，都是cost[i]

于是假設到達該點的距離為dis[i]則從該點能到的任何點j的值都是dis[j]=min(dis[j],dis[i]+cost[i]);

于是隻要按照dis[i]+cost[i]排序，目前最先的第一個點能到的點的距離一定都是最近的，這些點在這之後都不會再被更新了。

這樣隻要維護一個并查集壓縮路徑，或者維護一個set存可能還會被更新的點就好了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<functional>
using namespace std;
typedef long long LL;
const LL maxn = 200010;
LL n, T, d[maxn], l[maxn], r[maxn], c[maxn], ans, sum, fa[maxn];

void read(LL &res)
{
  char ch;
  while ((ch = getchar())<'0' || ch>'9');
  res = ch - '0';
  while ((ch = getchar()) >= '0'&&ch <= '9') res = res * 10 + ch - '0';
}

void write(LL x)
{
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

struct cmp
{
  bool operator()(const LL &a, const LL &b) const
  {
    return d[a] + c[a] > d[b] + c[b];
  }
};

LL find(LL x)
{
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}

void merge(LL x, LL y)
{
  x = find(x);  y = find(y);
  if (x == y) return;
  fa[x] = y;
}

void find_dis(LL x)
{
  d[x] = 0;
  priority_queue<LL, vector<LL>, cmp> p;
  p.push(x);
  while (!p.empty())
  {
    LL q = p.top(), ll, rr;   p.pop();

    ll = q - r[q]; rr = q - l[q];
    if (rr > 0) 
      for (LL j = max(ll, (LL)1);; j++)
      {
        j = find(j);
        if (j > min(rr, n)) break;
        if (d[j]>d[q] + c[q])
        {
          d[j] = d[q] + c[q];
          p.push(j);
        }
        merge(j, j + 1);
      }

    ll = q + l[q]; rr = q + r[q];
    if (ll <= n) 
      for (LL j = ll;; j++)
      {
        j = find(j);
        if (j > min(rr, n)) break;
        if (d[j]>d[q] + c[q])
        {
          d[j] = d[q] + c[q];
          p.push(j);
        }
        merge(j, j + 1);
      }
  }
}

int main()
{
  read(T);
  while (T--)
  {
    read(n);
    sum = 0;
    for (int i = 1; i <= n; i++) read(l[i]);
    for (int i = 1; i <= n; i++) read(r[i]);
    for (int i = 1; i <= n; i++) read(c[i]), sum += c[i];
    for (int i = 1; i <= n; i++) d[i] = sum + 1;
    for (int i = 1; i <= n + 1; i++) fa[i] = i;
    find_dis(1);
    for (int i = 1; i <= n; i++)
    {
      if (i > 1) putchar(' ');
      if (d[i] == sum + 1) putchar('-'), putchar('1');
      else write(d[i]);
    }
    putchar(10);
  }
  return 0;
}