(2015多校第6场)HDU5361–In Touch (Dijkstra应用) – No Rainbow

In Touch

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

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 (1in)

 

 

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 (1n2×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(0lirin,1ci109)

 

 

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
152 0 0 0 13 1 1 0 51 1 1 1 1
 

 

Sample Output
0 2 1 1 -1
 
大致思路: 从第一个点开始更新, 更新过的点缩成一个点, 因为在Dijkstra里 每次取出的都是最小的distance, 所以更新过的点 后面肯定不需要再次更新。更新一个点后加入堆中, 因为通过这个点可能更新别的点。
#pragma comment(linker, “/STACK:102400000,102400000”)
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <algorithm>
using namespace std;
const int MAXN = 2e5+10;
typedef long long LL;
typedef pair <LL, int>pli;
const LL inf = 1LL << 60;
LL L[MAXN], R[MAXN], cost[MAXN], dis[MAXN];
int dsu[MAXN];
void init (){
for (int i = 0 ; i< MAXN; i++){
dis[i] = inf;
dsu[i] = i;
}
}
int find (int s){
return dsu[s] = (dsu[s] == s ? s : find(dsu[s]));
}
int main() {
int n, T;
scanf (“%d”, &T);
while (T–) {
init();
scanf (“%d”, &n);
for (int i = 1; i <= n; i++) {
scanf (“%I64d”, L+i);
}
for (int i = 1; i <= n; i++) {
scanf (“%I64d”, R+i);
}
for (int i = 1; i <= n; i++) {
scanf (“%I64d”, cost+i);
}
init();
dis[1] = cost[1];
priority_queue<pli, vector<pli>, greater<pli> >Q;
Q.push(make_pair(0LL, 1));
while (!Q.empty()){
pli tmp = Q.top();
Q.pop();
int u = tmp.second;
for (int i = -1; i <= 1; i += 2){
int lf = L[u] * i + u;
int rg = R[u] * i + u;
if (lf > rg){
swap(lf, rg);
}
lf = max(lf, 1);
lf = min(lf, n + 1);
if (lf > rg){
continue;
}
for (int v = lf; ; v ++){
v = find(v);
if (v <= 0 || v > n || v > rg){
break;
}
if (dis[v] > dis[u] + cost[v]){
dis[v] = dis[u] + cost[v];
Q.push(make_pair(dis[v], v));
}
dsu[find(v)] = find(v + 1);
}
}
}
printf(“0”);
for (int i = 2; i <= n; i++) {
printf(” %I64d”, dis[i] != inf ? dis[i] – cost[i] : -1);
}
printf(“n”);
}
return 0;
}

  

 

本文链接:(2015多校第6场)HDU5361–In Touch (Dijkstra应用),转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量