Buongiorno, staveo cercando di risolvere questo problema, ma sbaglio alcuni testcase banali e non capisco perché.
La mia idea era la seguente (e controllando la soluzione ufficile (p.14) mi sembra sia praticamente la stessa della soluzione O(M log M)):
Creo un grafo simile a quello che mi viene danto in input, cioè collego A[i] e B[i] con un arco visto che ci sarà prima o poi una scala che li collegherà
Il peso di questo arco però è dato da inizio[i] + 1, così, se per caso lo dovessi percorrere, so che impiegherò inizio[i] + 1 + il tempo per arrivare a A[i] ad arrivare a B[i].
Faccio partire dijkstra sul grafo appena fatto e cerco la distanza dai nodi 0 e N-1, ma con un piccolo accorgimento: infatti quando espando un nodo e decido aggiornare i sui vicini, controllo che il tempo impiegato per raggiungere il nodo su cui mi trovo sia minore della scoparsa dell’arco che collega ogni nodo vicino. Se è così allora aggiorno la sua distanza e continuo con Dijkstra.
Sono consapevole che quando gli input diventano molto grandi è troppo lenta come soluzione, però la mia sbaglia anche su qualcuni input piccoli (es. testcase 005, 006, 007), quindi volevo sapere se il mio ragionamento aveva un senso o sto sbagliando qualcosa.
Ecco il codice:
struct tre{
int nodo;
int peso;
int fine;
};
constexpr long long unsigned int INF = 1e15;
int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
map<int, list<tre>> grafo;
for(int i = 0; i < M; i++) {
tre temp = {B[i], inizio[i] + 1, fine[i]};
grafo[A[i]].push_back(temp);
temp.nodo = A[i];
grafo[B[i]].push_back(temp);
}
//dijkstra
using p = pair<long long unsigned int, int>;
priority_queue<p> q;
vector<long long unsigned int> dist(N, INF);
bitset<500001> visited;
q.push({0, 0});
dist[0] = 0;
while(!q.empty()) {
int nodo = q.top().second;
q.pop();
if(visited[nodo]) continue;
visited[nodo] = 1;
for(auto e: grafo[nodo]) {
int b = e.nodo, w = e.peso;
if(e.fine > dist[nodo] && dist[nodo] + w < dist[b]) {
dist[b] = dist[nodo] + w;
q.push({-dist[b], b});
}
}
}
return dist[N - 1] != INF ? dist[N - 1]: -1;
}
La soluzione presentata dal testo ufficiale è quella O(M+T)
Ti sconsiglio di usare il contenitore bitset perché è molto lento, non staresti nei tempi richiesti
Questo dovrebbe essere quello che ti serve:
#include <list>
#include <limits>
#include <vector>
#include <queue>
#include <functional>
#include <iostream>
using namespace std;
struct arco{
int nodo,inizio,fine;
};
bool visited[500000];
int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]){
list<arco> adj[N];
vector<int> dist(N,numeric_limits<int>::max());
typedef pair<int,int> ip;
priority_queue<ip,vector<ip>,greater<ip>> q;
for(int i=0;i<M;i++){
arco temp={B[i],inizio[i],fine[i]};
adj[A[i]].push_back(temp);
temp.nodo=A[i];
adj[B[i]].push_back(temp);
}
q.push({0,0});
dist[0]=0;
while(!q.empty()){
int nodo=q.top().second;
q.pop();
if(visited[nodo])continue;
visited[nodo]=true;
for(list<arco>::iterator i=adj[nodo].begin();i!=adj[nodo].end();++i){
int next=(*i).nodo;
if((*i).fine>dist[nodo]){
if((*i).inizio<dist[nodo]){
if(dist[nodo]+1<dist[next]){
dist[next]=dist[nodo]+1;
q.push({dist[next],next});
}
}
else if((*i).inizio+1<dist[next]){
dist[next]=(*i).inizio+1;
q.push({dist[next],next});
}
}
//cout<<"nodo: "<<nodo<<" next: "<<next<<" dist nodo: "<<dist[nodo]<<" dist next: "<<dist[next]<<endl;
}
}
//for(int i=0;i<N;i++)printf("%d: %d\n",i,dist[i]);
if(dist[N-1]!=numeric_limits<int>::max()) return dist[N-1];
return -1;
}
Sono d’accordo che bitset possa essere leggermente piu lento a volte (anche se spesso puo essere piu veloce perche’ fa meno cache miss), in ogni caso non dovrebbe neanche lontanamente essere cosi lento da mandarti in tle (a meno che non fossi gia a pochi millisecondi dal tle I guess).
Comunque guardando la soluzione proposta se c’e’ da dire che qualche ds della stl e’ lenta piuttosto avrei detto quella map<int, list<tre>>
Ho provato a modificare il codice il minimo possibile, il principale problema nella tua soluzione immagino fosse una comprensione sbagliata del testo: per fare una rampa di scale il tempo impiegato e’ 1 e puoi solo iniziare a percorrerla a inizio[i], tu aggiungevi inizio[i] come se fosse il tempo impiegato a percorrere le scale.
Per questo motivo non erano necessari long long quindi gia che c’ero ho messo tutto a int.
Sostituire la map con vector per il grafo risolve anche il problema dei TLE.
Un paio di consigli:
Usa vector al posto di list, list e’ generalmente inutile
Usa priority_queue<T,vector<T>,greater<T>> per avere l’ordinamento dal piu piccolo cosi non devi stare a inserire le cose negate.
Usa array<int,2> al posto di pair<int,int> per una sintassi meno pesante (volendo puoi fare uguale anche al posto delle struct se poi ti ricordi cosa sono i campi)
per specificare unsigned, long long, unsigned long long, e altre cose del genere, non ti serve scriverci int
fai using ll = long long; per avere i long long senza scrivere 9 caratteri (o better using ll = int64_t;), stessa cosa per le counterpart unsigned
#include <bits/stdc++.h>
using namespace std;
struct tre{
int nodo;
int peso;
int fine;
};
const int INF = 1000000009;
int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
vector<list<tre>> grafo(N+1);
for(int i = 0; i < M; i++) {
tre temp = {B[i], inizio[i], fine[i]};
grafo[A[i]].push_back(temp);
temp.nodo = A[i];
grafo[B[i]].push_back(temp);
}
//dijkstra
using p = pair<int, int>;
priority_queue<p> q;
vector<int> dist(N, INF);
bitset<500001> visited;
q.push({0, 0});
dist[0] = 0;
while(!q.empty()) {
int nodo = q.top().second;
q.pop();
if(visited[nodo]) continue;
visited[nodo] = 1;
for(auto e: grafo[nodo]) {
int b = e.nodo, w = e.peso;
if(e.fine > dist[nodo] && max(dist[nodo],e.peso)+1<dist[b]) {
dist[b] = max(dist[nodo],e.peso)+1;
q.push({-dist[b], b});
}
}
}
return dist[N - 1] != INF ? dist[N - 1]: -1;
}