Ciao, sto provando a risolvere il problema corteo, ma totalizzo solo 22 causa TLE.
Come prima cosa calcolo tutte le distanze tra i nodi con una bfs che parte da ogni nodo. Poi faccio una binary search sulla soluzione. La funzione prova, chiamata nella binary search, simula tutti gli spostamenti possibili dei due cortei (se la distanza tra i due nuovi nodi è maggiore o uguale al valore passato alla funzione prova (cioè la distanza minima)). L’idea è corretta? Se si, qualcuno mi sa dire come ottimizzare?
Qui sotto il codice.
#include <bits/stdc++.h>
using namespace std;
int dist[1050][1050];
vector <int> grafo[1050];
bool vis[1050][1050];
struct att{
int nodo1, nodo2;
};
void bfs(int start)
{
queue < int > coda;
coda.push(start);
dist[start][start] = 0;
while(!coda.empty())
{
int nodo = coda.front();
coda.pop();
for(int i=0; i<grafo[nodo].size(); i++)
{
int figlio = grafo[nodo][i];
if(dist[start][figlio] > dist[start][nodo]+1)
{
coda.push(figlio);
dist[start][figlio] = dist[start][nodo]+1;
}
}
}
return;
}
// chi = 1..2
// dove = 0..N-1
void sposta(int chi, int dove);
int p1, d1, p2, d2, n;
bool prova(int minimo) /* BFS MUOVENDO ENTRAMBI I CORTEI */
{
if(dist[p1][p2] < minimo)
return false;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
vis[i][j] = false;
queue < att > coda;
coda.push({p1, p2});
vis[p1][p2] = true;
while(!coda.empty())
{
int nodo1 = coda.front().nodo1;
int nodo2 = coda.front().nodo2;
coda.pop();
vis[nodo1][nodo2] = true;
if(nodo1==d1 && nodo2==d2)
return true;
for(int i=0; i<grafo[nodo1].size(); i++)
{
int figlio = grafo[nodo1][i];
if(dist[figlio][nodo2] >= minimo && !vis[figlio][nodo2])
{
coda.push({figlio, nodo2});
}
}
for(int i=0; i<grafo[nodo2].size(); i++)
{
int figlio = grafo[nodo2][i];
if(dist[nodo1][figlio] >= minimo && !vis[nodo1][figlio])
{
coda.push({nodo1, figlio});
}
}
}
return false;
}
int pianifica(int N, int M, int P1, int D1, int P2, int D2, int A[], int B[]) {
for(int i=0; i<M; i++)
{
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
}
p1 = P1, d1 = D1, p2 = P2, d2 = D2;
n = N;
/* CALCOLO DISTANZE */
for(int i=0; i<N+10; i++)
{
for(int j=0; j<N+10; j++)
dist[i][j] = INT_MAX/4;
bfs(i);
}
/* BINARY SEARCH SULLA SOLUZIONE */
int lb = 0, ub = M+1;
while(lb+1 < ub)
{
int m=(lb+ub)/2;
if(prova(m))
lb = m;
else
ub = m;
}
return lb;
}
Grazie in anticipo,
Filippo.