Cod sursa(job #1978169)

Utilizator Razvanel6991Razvan Lazar Razvanel6991 Data 7 mai 2017 00:41:25
Problema Sate Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 3.48 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {
	static int N, M, X, Y;
	public class Pair{
		int destination, cost;
		
		public Pair(int destination, int cost){
			this.destination = destination;
			this.cost = cost;
		}
		
		public int getDestination(){
			return this.destination;
		}
		
		public int getCost(){
			return this.cost;
		}
		
		@Override
		public String toString() {
			String out = "";
			out += "(" + getDestination() + " [" + getCost() + "] )";
			return out;
		}
	}
	
	public class Graph {
		Map<Integer, ArrayList<Pair>> graph;
		
		public Graph(){
			graph = new HashMap<>();
		}
		
		public void addNode(int node){
			graph.put(node, new ArrayList<Pair>());
		}
		
		public void addEdge(int src, int dest, int cost) {
			graph.get(src).add(new Pair(dest, cost));
			graph.get(dest).add(new Pair(src, cost));
		}
		
		public ArrayList<Pair> getNeighbor(int node){
			return graph.get(node);
		}
		
		@Override
		public String toString() {
			String out = "";
			for(Integer node : graph.keySet()) {
				out += "Nodul: " + node + " ===" + graph.get(node) + "\n";
			}
			return out;
		}
	}
	
	public static void readInput(Graph g){
		try{ BufferedReader br = new BufferedReader(new FileReader("sate.in"));
			// Citim datele din fisier
			String input;
			String[] parseInput;
			
			input = br.readLine();
			parseInput = input.split(" ");
			N = Integer.parseInt(parseInput[0]);
			M = Integer.parseInt(parseInput[1]);
			X = Integer.parseInt(parseInput[2]);
			Y = Integer.parseInt(parseInput[3]);
			
			// adaugam nodurile in graf
			for(int i = 1; i <= N; i++){
				g.addNode(i);
			}
			
			// adaugam muchiile in graf
			for(int i = 0; i < M; i++){
				input = br.readLine();
				parseInput = input.split(" ");
				
				int source, dest, cost;
				source = Integer.parseInt(parseInput[0]);
				dest = Integer.parseInt(parseInput[1]);
				cost = Integer.parseInt(parseInput[2]);
				g.addEdge(source, dest, cost);
			}
		} 
		catch (Exception e) {
			e.printStackTrace();
		}
		
	}
	
	public static int[] doBFS(Graph g, int source, int destination){
		boolean[] visited = new boolean[N];
		int[] distances = new int[N];
		Queue<Integer> q = new LinkedList<>();
		
		// setam distantele si adaugam nodurile in graf
		for(int i = 0; i < N; i++){
			distances[i] = Integer.MAX_VALUE;
		}
		
		distances[source - 1] = 0;
		q.add(source);
		visited[source - 1] = true;

		while(!q.isEmpty()){
			int node = q.poll();
			//System.out.println("Scoatem din coada nodul " + node + g.getNeighbor(node));
			
			for(Pair p : g.getNeighbor(node)){
				//System.out.println("lUAM VECINII");
				int dest = p.getDestination();
				//System.out.println("Pentru nodul de mai sus avem dest " + dest);
				if(!visited[dest - 1]){
					distances[dest - 1] = distances[node - 1] + p.getCost();
					if(dest == destination){
						return distances;
					}
					q.add(dest);
					visited[dest - 1] = true;
				}
			}
		}
		
		
		return distances;
	}
	
	public static void main(String []args){
		Main s = new Main();
		Graph g = s.new Graph();
		int[] distances;
		readInput(g);
		
		distances = doBFS(g, X, Y);
		try{BufferedWriter bw = new BufferedWriter(new FileWriter("sate.out"));
		
			bw.write(String.valueOf(distances[Y - 1]));
			bw.flush();
		}
		catch (Exception e) {
			e.printStackTrace();
		}
		//System.out.println(g);
	}
}