Maior Menor Caminho

maiormenorcaminho.cpp

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define MAXN 3030
#define INF 0x3f3f3f3f

#define PB push_back

int n, m, dist[MAXN][MAXN], alpha[MAXN][3], beta[MAXN][3], maior, v1, v2, v3, v4;

vector<int> lista[MAXN];

// BFS para calcularmos as distâncias entre vértices
void bfs(int ori){
	
	queue<int> fila;
	fila.push(ori);
	dist[ori][ori]=0;
	
	while(!fila.empty()){
		
		int v=fila.front(); fila.pop();
		
		for(int i=0; i<lista[v].size(); i++){
			
			int u=lista[v][i];
			
			if(dist[ori][u]==-1){
				
				dist[ori][u]=dist[ori][v]+1;
				fila.push(u);
			}
		}
	}
}
	
int main(){
	
	memset(dist, -1, sizeof dist);
	
	scanf("%d %d", &n, &m);
	
	// leio todas as arestas
	for(int i=1; i<=m; i++){
		
		int v, u;
		scanf("%d %d", &v, &u);
		
		lista[v].PB(u);
	}
	
	// faço BFS em todos os vértices para calcular todas as distâncias
	for(int i=1; i<=n; i++) bfs(i);
	
	// calculo os valores de alpha de cada vértice i
	for(int i=1; i<=n; i++){
		
		// procurando um j que supere algum dos valores salvos em alpha[i]
		for(int j=1; j<=n; j++){
			
			// para isso, calculo a menor distância em alpha[i]
			int menor=INF, idx=-1;
			for(int k=0; k<3; k++) if(dist[alpha[i][k]][i]<menor) menor=dist[alpha[i][k]][i], idx=k;
			
			// e checo se d(j,i) a supera
			if(dist[j][i]>menor) alpha[i][idx]=j;
		}
	}
	
	// de maneira semelhante, calculo os valores de beta
	for(int i=1; i<=n; i++){
		
		for(int j=1; j<=n; j++){
			
			int menor=INF, idx=-1;
			
			for(int k=0; k<3; k++) if(dist[i][beta[i][k]]<menor) menor=dist[i][beta[i][k]], idx=k;
			
			// mas, agora, checo a d(i,j), não d(j,i)
			if(dist[i][j]>menor) beta[i][idx]=j;
		}
	}
	
	// agora testo todos os possíveis valores de A, B, C e D
	for(int i=0; i<3; i++)
		for(int v=1; v<=n; v++)
			for(int u=1; u<=n; u++)
				for(int j=0; j<3; j++){
					
					int k=alpha[v][i], q=beta[u][j];
					
					// se houver alguma repetição, tal escolha de A, B, C e D não é possível
					if(k==v or k==u or k==q) continue;
					
					if(v==u or v==q) continue;
					
					if(u==q) continue;
					
					// se algum deles for inalcançãvel a partir do anterior, também não é possível
					if(dist[k][v]<0 or dist[v][u]<0 or dist[u][q]<0) continue;
					
					// calculo o tamanho da rota
					int d=dist[k][v]+dist[v][u]+dist[u][q];
					
					// e nvejo se ela é  maior
					if(d>maior) maior=d, v1=k, v2=v, v3=u, v4=q;
				}
	
	// por fim, imprimo a reposta
	printf("%d %d %d %d\n", v1, v2, v3, v4);
	
	return 0;
}