Pagini recente » Cod sursa (job #448073) | Cod sursa (job #211893) | Cod sursa (job #1455310) | Cod sursa (job #2219422) | Cod sursa (job #1978169)
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);
}
}