|
++i)vis[i] = false;
for(int i = 0; i <= n; ++i)dis[i] = linf;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
node t; int u;
while(!pq.empty())
{
t = pq.top(); pq.pop();
u = t.v;
if(vis[u])continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
printf("0");
for(int i = 2; i <= n; ++i)printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn << 3];
void build(int rt, int l, int r, bool flag)
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag)
{
if(L > r || R < l)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down; //, up;
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; t = read();
while(t--)
{
int n; n = read();
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();
cnt = n;
dijkstra.init(n << 3);
down.build(1, 1, n, false);
// up.build(1, 1, n, true);
for(int i = 1; i <= n; ++i)
{
down.addedge(1, 1, n, i, l[i] + i, r[i] + i, c[i], false);
down.addedge(1, 1, n, i, max(1, i - r[i]), max(1, i - l[i]), c[i], false);
}
dijkstra.dijkstra(1, cnt);
dijkstra.print(n);
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
(end)
|