hdu 5361 2015多校联合训练赛#6 最短路

时间：2023-03-08 23:49:15
hdu 5361 2015多校联合训练赛#6 最短路

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 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
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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<set>

using namespace std;

#define maxn 200007

#define ll long long

int lp[maxn],rp[maxn];

ll cosw[maxn];

ll dist[maxn];

set<int> 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<Node> 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<int>::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;

}

相关文章