HDu 5361

真的好难

2024-07-03 帮助1人

In Touch

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

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 .

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=2*10e5 10;
const __int64 inf=(1LL<<62);
__int64 dist[maxn];
int l[maxn],r[maxn],c[maxn],pre[maxn];

struct Node
{
    int x;
    __int64 dist;
    friend bool operator < (const Node &a,const Node &b)
    {
        return a.dist>b.dist;
    }
};
priority_queue <Node> q;

int fin(int x)
{
    int r=x;
    while(r!=pre[r])
    {
        r=pre[r];
    }
    int k=x;
    while(pre[k]!=r)
    {
        int j=pre[k];
        pre[k]=r;
        k=j;
    }
    return r;
}

void join(int x,int y)
{
    int fx=fin(x);
    int fy=fin(y);
    if(fx!=fy)
        pre[fx]=fy;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        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("%d",&c[i]);
        for(int i=1;i<=n 1;i  )
        {
            dist[i]=inf;
            pre[i]=i;
        }
        Node a;
        dist[1]=c[1];
        a.x=1,a.dist=0;
        q.push(a);
        while(!q.empty())
        {
            Node b=q.top();
            q.pop();
            int num=b.x;
            for(int i=-1;i<=1;i =2)
            {
                int L=num l[num]*i;
                int R=num r[num]*i;
                if(L>R) swap(L,R);
                if(L>n||R<=0)continue;
                L=max(L,1),R=min(R,n);
                for(int k=L;k<=R;k  )
                {
                    k=fin(k);
                    if(k>R)break;
                    if(dist[k]>dist[num] c[k])
                    {
                        dist[k]=dist[num] c[k];
                        Node c;
                        c.x=k,c.dist=dist[k];
                        q.push(c);
                    }
                    join(k,k 1);
                }
            }
        }
        printf("0");
        for(int i=2;i<=n;i  )
        {
            if(dist[i]==inf)
                printf(" -1");
            else
                printf(" %I64d",dist[i]-c[i]);
        }
        printf("\n");
    }
    return 0;
}

这篇好文章是转载于：学新通技术网

HDu 5361

In Touch

photoshop保存的图片太大微信发不了怎么办

photoshop扩展功能面板显示灰色怎么办

word里面弄一个表格后上面的标题会跑到下面怎么办

《学习通》视频自动暂停处理方法

TikTok加速器哪个好免费的TK加速器推荐

Android 11 保存文件到外部存储，并分享文件

excel下划线不显示怎么办

微信公众号没有声音提示怎么办

微信运动停用后别人还能看到步数吗

excel打印预览压线压字怎么办