Skip to content

Instantly share code, notes, and snippets.

@hinckel
Created September 5, 2016 02:21
Show Gist options
  • Save hinckel/76569d2e12a271aacf56e9745e8c5d3b to your computer and use it in GitHub Desktop.
Save hinckel/76569d2e12a271aacf56e9745e8c5d3b to your computer and use it in GitHub Desktop.
package ExercicioAero;
import java.io.*;
/**
*
* @author Luiz Felipe Hinckel
*/
public class ExercicioAero {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws FileNotFoundException, IOException {
try {
BufferedReader br = new BufferedReader(new FileReader(new File("C://entrada.txt")));
int vetor[] = new int[100];
for (int i : vetor) {
vetor[i] = 0;
}
while(br.ready()) {
String linha = br.readLine();
System.out.println(linha);
}
for (int i : vetor) {
System.out.println( vetor[i] );
}
} catch (FileNotFoundException fnfe) {
System.out.println("Precisamos de um arquivo de entrada no seu C!");
}
}
}
@hinckel
Copy link
Author

hinckel commented Sep 5, 2016

package pedagio;

import java.io.;
import java.util.
;

/**

  • http://br.spoj.com/problems/PEDAGIO/
    *

  • @author Jean Pereira
    */
    public class Main {

    public static void main(String[] args) {

    //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //BufferedReader br = new BufferedReader(new FileReader(new File("/Users/jeanp/Projects/SPOJ/src/pedagio", "pedagio.in")))
    try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    
        int testIdx = 1;
        while (br.ready()) {
            String line = br.readLine();
    
            if (line.equals("0 0 0 0")) {
                return;
            }
    
            String[] split = line.split(" ");
    
            int C = Integer.parseInt(split[0]);//numero de cidades
            int E = Integer.parseInt(split[1]);//numero de estradas
            int L = Integer.parseInt(split[2]);//cidade onde está 1...C
            int P = Integer.parseInt(split[3]);//numero maximo de pedagios
            int[][] adjancencias = new int[C][C];//matriz de adjancencias entre as cidades
    
            for (int i = E; i > 0; i--) {
                line = br.readLine();
                split = line.split(" ");
                int o = Integer.parseInt(split[0]);
                int d = Integer.parseInt(split[1]);
                adjancencias[o-1][d-1] = 1;
                adjancencias[d-1][o-1] = 1;//mao dupla
            }
    
            int[] distanceFrom = bfs(adjancencias, L);
    
            System.out.println("Teste "+testIdx);
            printDistances(P, distanceFrom);
    
            System.out.println("");
            testIdx++;
    
        }
    
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }
    

    }

    private static void printDistances(int maxDistance, int[] distanceFrom) {
    int city = 1;
    StringBuilder sb = new StringBuilder();
    for (int d : distanceFrom) {
    if (d > 0 && d <= maxDistance) {
    if (sb.length() > 0) {
    sb.append(" ");
    }
    sb.append(city);
    }
    city++;
    }
    System.out.println(sb.toString());
    }

    private static int[] bfs(int[][] adjancencias, int o) {

    int[] distance = new int[adjancencias.length];
    List<Integer> visited = new ArrayList<>();
    Queue Q = new LinkedList<>();
    Q.add(o);
    
    while (!Q.isEmpty()) {
        Integer v = (Integer) Q.poll();
        visited.add(v);
    
        Queue adj = getAdjacencias(adjancencias[v-1]);
        while (!adj.isEmpty()) {
            Integer w = (Integer) adj.poll();
            if (!visited.contains(w)) {
                distance[w-1] = distance[v-1] + 1;
                Q.add(w);
                visited.add(w);
            }
        }
    }
    
    return distance;
    

    }

    private static Queue getAdjacencias(int[] adjacencias) {
    Queue Q = new LinkedList<>();
    int cidade = 1;
    for (int c : adjacencias) {
    if (c>0) {
    Q.add(cidade);
    }
    cidade++;
    }

    return Q;
    

    }
    }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment