|
{
return w > r.w;
}
}tmp;
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue<node> pq;
void dijkstra(int s, int n)
{
for(int i = 0; i <= n; ++i)dis[i] = linf;
for(int i = 0; i <= n; ++i)vis[i] = false;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
while(!pq.empty())
{
tmp = pq.top(); pq.pop();
if(vis[tmp.v])continue;
vis[tmp.v] = true;
for(int i = head[tmp.v]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(dis[v] > dis[tmp.v] + edge[i].w)
{
dis[v] = dis[tmp.v] + edge[i].w;
pq.push(node(v, dis[v]));
}
}
}
}
int cnt;
void build(int rt, int l, int r)
{
if(l == r)
{
cnt = max(cnt, rt + n);
ADDEDGE(rt + n, l, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
ADDEDGE(rt + n, (rt << 1) + n, 0);
ADDEDGE(rt + n, (rt << 1 | 1) + n, 0);
}
int L, R, W, U;
void addedge(int rt, int l, int r)
{
if(L > r || l > R)return;
if(L <= l && r <= R)
{
ADDEDGE(U, rt + n, W);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r);
}
int l[maxn], r[maxn], c[maxn];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// int t; cin >> t;
// int t; scanf("%d", &t);
int t; t = read();
while(t--)
{
// cin >> n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)l[i] = read();
for(int i = 1; i <= n; ++i)r[i] = read();
for(int i = 1; i <= n; ++i)c[i] = read();
init(n << 3);
cnt = 0;
build(1, 1, n);
for(int i = 1; i <= n; ++i)
{
U = i;
L = i + l[i]; R = i + r[i]; W = c[i];
addedge(1, 1, n);
L = i - r[i]; R = i - l[i];
addedge(1, 1, n);
}
dijkstra(1, cnt);
printf("0");
for(int i = 2; i <= n; ++i)
printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
AC_2
（不加快读也没事，，，就是不能memset，，，卡memset好恶心，，，，
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //快读
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct Dijkstra
{
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
// memset(head, -1, sizeof head);
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void addedge(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v; ll w;
node(){}
node(int _v, ll _w):v(_v), w(_w){}
const bool operator<(const node &r)const
{
return w > r.w;
}
};
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue<node> pq;
void dijkstra(int s, int n)
{
// memset(vis, false, sizeof vis);
// memset(dis, inf, sizeof dis);
for(int i = 0; i <= n;
|