У меня проблемы с ограничением памяти и ошибкой исполнения!
Моя идея
Cоздать ребра между (i,i+1) с весом 0 ( Потому что мы можем перемещаться в острове ) l<=i<r и создать ребра между (i,i+x) l<=i<=r с весом 1 ( Потому что прыгая на +x координат мы переходим на новый остров а вес 1 потому что нам надо найти минимальное количество островов которые он посетить ). И найти кратчайший путь от минимальной левой границы до максимальной правой границы островов в моем случае с помощью Дейкстры c set-ом. Answer+1 потому что есть остров котором он изначально стоял. Примечание: я знаю что у меня очень много ребер помагите найти ошибку!!!
Вот как я это реализовал:
Проходит на 35 баллов первая и третья подзадача
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void iosbase(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
vector<pair<ll, ll>> g[300100];
ll d[300100],l[300100],r[300100];
int main() {
iosbase();
ll m,x,n=0,s; cin>>m>>x;
for(ll i=0; i<m; i++){
cin>>l[i]>>r[i];
n=max(n, r[i]);
s=min(s, l[i]);
}
for(ll i=0; i<m; i++){
for(ll j=l[i]; j<r[i]; j++){
g[j].push_back(make_pair(j+1, 0));
g[j+1].push_back(make_pair(j, 0));
if(j+x <= n){
g[j].push_back(make_pair(j+x, 1));
g[j+x].push_back(make_pair(j, 1));
}
}
if(r[i]+x <= n){
g[r[i]].push_back(make_pair(r[i]+x, 1));
g[r[i]+x].push_back(make_pair(r[i], 1));
}
}
for(ll i = 0; i <= n; i++) {
d[i] = 1e18;
}
d[s] = 0;
set < pair<ll, ll> > S;
for(ll i = 1; i <= n; i++) {
S.insert(make_pair(d[i], i));
}
for(ll it=0; it < n; it++) {
ll v = (*S.begin()).second;
S.erase(S.begin());
for(ll i = 0; i < g[v].size(); i++) {
ll to = g[v][i].first;
ll w = g[v][i].second;
if(d[to] > d[v] + w) {
S.erase(make_pair(d[to], to));
d[to] = d[v] + w;
S.insert(make_pair(d[to], to));
}
}
}
if(d[n] == 1e18) {
cout << -1 << "\n";
} else {
cout<<d[n]+1<<'\n';
}
}