Pagini recente » Cod sursa (job #225305) | Cod sursa (job #2872562)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
struct muchie{
int y,cost;
};
const int N = 1e5 + 2;
vector <muchie> v[2*N];
vector<long long> cost_lift;
vector<long long>cladire_lim_dreapta;
long long dp[2*N];
bitset<2*N>inq;
struct criteriu{
bool operator()(int a, int b){
return dp[a]>dp[b];
}
};
priority_queue<int, vector<int>,criteriu>q;
bool intersecteaza(long long a, long long b, long long c, long long d){
return ((a<=c && c<=b) || (a<=d && d<=b) || (c<=a && a<=d) || (c<=b && b<=d)) ;
}
void dijkstra(){
long long x = 0;
q.push(x);
inq[x] = true;
while(!q.empty()){
// cout<<q.size()<<'\n';
x = q.top();
q.pop();
inq[x] = false;
for(auto y:v[x]){
// cout<<x<<' '<<y.y<<' '<<y.cost<<'\n';
if((dp[y.y]>dp[x] + (long long)y.cost )|| dp[y.y] == 0){
dp[y.y] = dp[x] + (long long)y.cost;
if(!inq[y.y]){
q.push(y.y);
inq[y.y] = true;
}
}
}
}
}
int main() {
ifstream in("superhedgy.in");
ofstream out("superhedgy.out");
muchie add;
long long n,m,l,h;
long long h_anterior = 0,h_ultim_sus, h_ultim_jos;
in>>n;
long long c;
cost_lift.push_back(0);
cladire_lim_dreapta.push_back(0);
for(int i=1;i<=n;i++){
in>>l>>h>>c;
cost_lift.push_back(c);
h_ultim_sus = h;
cladire_lim_dreapta.push_back(0);
cladire_lim_dreapta[i] = cladire_lim_dreapta[i-1] + l;
add.y = i;
add.cost =max( h-h_anterior,h_anterior-h);
v[i-1].push_back(add);
h_anterior = h;
}
h_anterior = 0;
long long cladire = 1;
long long st_cladire = 1;
long long dr_cladire = cladire_lim_dreapta[1];
long long st_cladire_jos = 1;
long long dr_cladire_jos = 1;
in>>m;
cladire_lim_dreapta.push_back(0);
cladire_lim_dreapta.push_back(0);
cladire_lim_dreapta.push_back(0);
//cout<<cladire_lim_dreapta[n+1];
for(int i=2;i<=m+1;i++){
in>>l>>h>>c;
h_ultim_jos = h;
cladire_lim_dreapta.push_back(0);
cladire_lim_dreapta[i+n] = cladire_lim_dreapta[i+n-1] + l;
st_cladire_jos = cladire_lim_dreapta[i+n-1]+1;
dr_cladire_jos = cladire_lim_dreapta[i+n];
while(intersecteaza(st_cladire_jos, dr_cladire_jos,st_cladire,dr_cladire) && cladire<=n){
// cout<<cladire<<' '<<i+n<<'\n';
add.y = cladire;
add.cost = cost_lift[cladire] + c;
// cout<<cost_lift[cladire] + c<<'\n';
v[i+n].push_back(add);
add.y = i+n;
v[cladire].push_back(add);
cladire++;
st_cladire = cladire_lim_dreapta[cladire-1]+1;
dr_cladire = cladire_lim_dreapta[cladire];
// cout<<cladire<<' '<<st_cladire<<' '<<dr_cladire<<'\n';
}
if(st_cladire-1>dr_cladire_jos)
cladire--;
st_cladire = cladire_lim_dreapta[cladire-1]+1;
dr_cladire = cladire_lim_dreapta[cladire];
add.y = i+n;
add.cost =max( h-h_anterior,h_anterior-h);
if(i==2){
v[0].push_back(add);
}
else
v[i+n-1].push_back(add);
h_anterior = h;
}
add.y = n+m+3;
add.cost = h_ultim_sus;
v[n].push_back(add);
add.cost = h_ultim_jos;
v[n+m+1].push_back(add);
long long rez = cladire_lim_dreapta[n];
cladire_lim_dreapta.clear();
cost_lift.clear();
dijkstra();
out<<dp[n+m+3] +rez;
return 0;
}