È da giorni che ormai sto provando a risolvere questo problema. La soluzione migliore a cui sono arrivato è stata fare una bsearch da 0 al numero massimo di volontarie presenti in un arco del grafo, e una bfs che cerca l’esistenza di un percorso con massimo X volontarie, dove X è il numero ricavato dalla bserarch.
Con questo algoritmo totalizzo 15 punti, e oltre non riesco a spingermi per via del limite di tempo.
Ho notato che solamente 16 persone l’hanno risolto, quindi magari è davvero tosto come problema. Qualcuno che possa aiutarmi?
Okay, un piccolo indirizzamento.
Se ho ben capito, fai la ricerca binaria sulla risposta. Se un certo valore V è accettabile come risposta, lo saranno anche tutti quelli \leq V; viceversa se non è accettabile, non lo saranno neanche tutti quelli \geq V. La risposta è il minimo V tale che V sia accettabile. Cosa intendiamo per accettabile? Intendiamo che esista un percorso da S ad E, che passi su strade con al massimo V volontarie, e che sia lungo al massimo T. Ora il punto è verificare se tale percorso esista. Tu fai una bfs, ma tale algoritmosui grafi pesati la bfs non trova il percorso minimo. Dovresti invece pensare, ogni volta che vuoi verificare se un valore V sia accettabile, come fare per trovare un percorso che non passi su archi con >V volontarie e sia lungo meno di T.
Innanzitutto ti ringrazio per l’aiuto.
Però non mi è chiara la prima frase. Se un certo valore V è accettabile come risposta, lo saranno anche tutti quelli ≥ V, non il contrario, o sbaglio?
Comunque prima di pubblicare il post avevo provato ad applicare dijkstra sul tempo per la ricerca del percorso minimo, sempre utilizzando la ricerca binaria per il massimo valore V con cui cercare il percorso, salvando i risultati in una matrice grande N * (K + 1). Salvavo infatti il tempo minimo per arrivare al nodo B[i], nella riga B[i] e nella colonna relativa al numero di biglietti con cui ci arrivavo.
Con questo algoritmo però il tempo d’esecuzione aumentava ancora di più rispetto alla bfs ripetuta finché non trovavo il minimo V accettabile, quindi credevo fosse un algoritmo peggiore.
Okay tutto risolto. Ho ottenuto i 100 punti facendo qualche piccola aggiunta al codice descritto nel messaggio sopra. 
Potresti spiegare come hai fatto?
Io non sono riuscito ad ottenere più di 68 punti.
Perché non provi a descrivermi quello che hai fatto? Così vediamo dove si può migliorare 
Faccio la ricerca binaria sulla risposta e controllo ogni volta se il numero di volontarie è accettabile applicando dijkstra come descritto da te nel messaggio sopra
Okay. Provo a darti un piccolo indizio.
Prendiamo per esempio che ci sono solamente 2 valori V[i] all’interno del nostro grafo: 0 e 10^9. Tu faresti la ricerca binaria partendo da metà, poi ancora metà e così via, continuando ad applicare dijkstra su valori che ovviamente, se non sono accettabili la prima volta, non lo saranno mai fino a quando raggiungi finalmente l’ultimo valore, 10^9. Credi di riuscire a trovare un modo per evitare di applicare la ricerca binaria su valori quindi non presenti nel tuo grafo?
Io faccio 96 punti sbagliando solo l’ultimo testcase 
#include <vector>
#include <queue>
#include <stdio.h>
#include <limits>
#include <set>
using namespace std;
#define MAXN 1010
#define MAXK 76
const int INF = numeric_limits<int>::max();
int N;
struct arco_t {
int v, t_piedi, t_bus, n_volontarie;
};
vector<arco_t> G[MAXN];
int distances[MAXN][MAXK];
struct info_t {
int n, t, k;
bool operator< (const info_t& rhs) const {
return t > rhs.t;
}
};
int dijkstra(int S, int E, int T, int K, int maxV) {
for (int i = 0; i <= N; i++)
for (int j = 0; j <= K; j++)
distances[i][j] = INF;
priority_queue<info_t> Q;
Q.push({S, 0, K});
while (!Q.empty()) {
int n = Q.top().n,
t = Q.top().t,
k = Q.top().k;
Q.pop();
if (t > T) continue;
//printf("Nodo %d (t=%d, k=%d)\n", n, t, k);
if (t >= distances[n][k]) continue;
distances[n][k] = t;
for (auto x : G[n]) {
//printf("\tArco %d -> %d (v: %d, t_b: %d, t_p: %d)\n", n, x.v, x.n_volontarie, x.t_bus, x.t_piedi);
if (x.n_volontarie > maxV) {
if (k > 0 && (t + x.t_bus <= T)) {
Q.push({x.v, t + x.t_bus, k-1});
}
continue;
}
if ((t + x.t_piedi) <= T) Q.push({x.v, t + x.t_piedi, k});
if (k > 0 && (t + x.t_bus) <= T) Q.push({x.v, t + x.t_bus, k-1});
}
}
int shortest = INF;
for (int i = 0; i <= K; i++) {
//printf("distances[%d][%d] = %d\n", E, i, distances[E][i]);
shortest = min(shortest, distances[E][i]);
}
return shortest;
}
int avoid_volunteers(int subtask, int N, int M, int K, int S, int E, int T, int A[], int B[], int W[], int P[], int V[]) {
::N = N;
int low = INF;
int high = 0;
set<int> possibleV;
for (int i = 0; i < M; i++) {
G[A[i]].push_back({B[i], W[i], P[i], V[i]});
G[B[i]].push_back({A[i], W[i], P[i], V[i]});
low = min(low, V[i]);
high = max(high, V[i]);
possibleV.insert(V[i]);
}
vector<int> vpV(possibleV.begin(), possibleV.end());
low = 0;
high = vpV.size() - 1;
while (low <= high) {
int mid = low + (high-low) / 2;
int r = dijkstra(S, E, T, K, vpV[mid]);
if (r == INF) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
if (low >= vpV.size()) return -1;
return vpV[low];
}
1 Mi Piace
Ciao, con sbagliando intendi dire che va in Timeout?
Se è così probabilmente è perché Dijkstra l’hai reso più lungo di quello che serve:
suggerimento:
Puoi interrompere l’algoritmo non appena raggiungi E in un tempo <= T.
Se ciò non accade restituisci INF a priori.
1 Mi Piace
Ho aggiunto un’if prima dell’iterazione degli archi:
if (n == E) return t;
Ma niente, sempre l’ultimo caso in timeout
EDIT: Ho fixato aggiungendo degli if prima dei push in modo da non aggiungerli alla coda se c’era già una distanza minore
1 Mi Piace
A questo punto se non va in timeout di troppo potresti provare a ottimizzare il più possibile il codice (per esempio sostituendo possibleV e vpV con l’array V[] dopo che lo hai sottoposto a std::sort()), se ciò non fosse sufficiente dovresti provare a migliorare la tua implementazione di Dijkstra o cercare un altro algoritmo per il cammino minimo più efficiente (quantomeno in questo caso).
Io personalmente Dijkstra non l’ho usato ma credo che gli altri che hanno risolto il problema l’abbiano usato con qualche miglioramento solo che non so come migliorarlo, dovrei pensarci un po’ su.
Leggi l’edit 
In ogni caso fare un vector e poi il sort sarebbe stato più lento perché avrei dovuto controllare la presenza di elementi doppi e il sort avrebbe portato comunque la complessità a NlogN (stessa di usare il set)
1 Mi Piace
Sorvoliamo 
Come ribadisce il tipo che ha inventato il C++ nel suo libro: “Non fatevi ingannare dalle complessità teoriche, misurate!”
Scherzi a parte, non serve creare un nuovo vettore, io ho usato direttamente V (e non ho fatto nemmeno il controllo per gli elementi duplicati poiché quando avevo provato a metterlo aveva qualche difetto e inoltre non mi è nemmeno servito.
Credo che questi due cicli prendano un sacco di tempo, magari se non riesci a migliorare l’algoritmo puoi provare a trovare un modo per rendere più veloce questa parte.
Questo serve a qualcosa?
P.S.: non centra nulla con questo problema in particolare ma tutte le implementazioni di Dijkstra funzionano tramite “rilassamenti” continui?
100/100! 
Grazie per l’aiuto.
Non c’è di che 
Sì hai ragione, ho confuso maggiore e minore