UVa 544

From Algorithmist
Jump to navigation Jump to search

544 - Heavy Cargo[edit]

Summary[edit]

Modified dijkstra allgorithm

Solution

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out, true);
		int set = 0;
		
		Map<String, Node> cityNodeMap = new HashMap<>();
		
		while (in.hasNextInt()) {
			set++;
			int n = in.nextInt();// ceties
			int m = in.nextInt();// roads
			
			if (n == 0 && m == 0) {
				out.flush();
				out.close();
				return;
			}
			out.println("Scenario #" + set);
			
			// last city index
			int index = 0;
			
			List<Node> nodeList = new ArrayList<Node>();
			for (int i = 0; i < m; i++) {
				String from = in.next();
				String to = in.next();
				int weigth = in.nextInt();
				
				Node a, b;
				
				if ((a = cityNodeMap.get(from)) == null) {
					a = new Node(index++, from);
					cityNodeMap.put(from, a);
				}
				if ((b = cityNodeMap.get(to)) == null) {
					b = new Node(index++, to);
					cityNodeMap.put(to, b);
				}
				Edge e1 = new Edge(a, b, weigth);
				Edge e2 = new Edge(b, a, weigth);
				a.getEdges().add(e1);
				b.getEdges().add(e2);
			}
			String start = in.next();
			String end = in.next();
			
			Node startNode = cityNodeMap.get(start);
			Node endNode = cityNodeMap.get(end);

			
			// dijkstra
			PriorityQueue<Node> queue = new PriorityQueue<Node>(n, new NodeComparator());
			Collection<Node> nl = cityNodeMap.values();
			for (Iterator iterator = nl.iterator(); iterator.hasNext();) {
				Node node = (Node) iterator.next();
				node.setCurrentCost(0);
				queue.add(node);
			}
			queue.remove(startNode);
			startNode.setCurrentCost(Integer.MAX_VALUE);
			queue.add(startNode);

			while (!queue.isEmpty()) {
				Node currentNode = queue.remove();
				List<Edge> edges = currentNode.getEdges();
				for (int i = 0; i < edges.size(); i++) {
					Edge e = edges.get(i);

					Node src = e.getStart();
					Node dst = e.getEnd();
					int cost = e.getCost();

					if (dst.getCurrentCost() < Math.max(dst.getCurrentCost(), Math.min(src.getCurrentCost(), cost))) {
						queue.remove(dst);
						dst.setCurrentCost(Math.max(dst.getCurrentCost(), Math.min(src.getCurrentCost(), cost)));
						dst.setPreviousNode(src);
						queue.add(dst);
					}
				}
			}


			int currentCost = endNode.getCurrentCost();

			out.println(currentCost + " tons");
			out.println("");
		}

		out.flush();
		out.close();

	}
}

class Edge {
	private Node start;
	private Node end;
	private int cost;

	public Edge(Node start, Node end, int cost) {
		this.start = start;
		this.end = end;
		this.cost = cost;
	}

	public Node getStart() {
		return start;
	}

	public void setStart(Node start) {
		this.start = start;
	}

	public Node getEnd() {
		return end;
	}

	public void setEnd(Node end) {
		this.end = end;
	}

	public int getCost() {
		return cost;
	}

	public void setCost(int cost) {
		this.cost = cost;
	}
}

class Node {
	private int n;
	private List<Edge> edges = new ArrayList<Edge>();

	private int currentCost = 0;
	private Node previousNode;
	private String name;

	public Node(int n, String name) {
		this.n = n;
		this.name = name;
	}

	private boolean solved = false;
	
	
	
	
	public boolean isSolved() {
		return solved;
	}







	public void setSolved(boolean solved) {
		this.solved = solved;
	}







	@Override
	public String toString() {
		return "Node [n=" + n + ", currentCost=" + currentCost
				+ ", previousNode=" + previousNode + ", name=" + name + "]";
	}







	public void addEdge(Edge e) {
		edges.add(e);
	}

	public List<Edge> getEdges() {
		return edges;
	}

	public int getCurrentCost() {
		return currentCost;
	}

	public void setCurrentCost(int currentCost) {
		this.currentCost = currentCost;
	}

	public Node getPreviousNode() {
		return previousNode;
	}

	public void setPreviousNode(Node previousNode) {
		this.previousNode = previousNode;
	}
	
	

	public int getN() {
		return n;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + n;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node other = (Node) obj;
		if (n != other.n)
			return false;
		return true;
	}

}

class NodeComparator implements Comparator<Node> {

	public int compare(Node o1, Node o2) {
		if (o1.getCurrentCost() == o2.getCurrentCost()) {
			return 0;
		} else if (o1.getCurrentCost() > o2.getCurrentCost()) {
			return -1;
		} else if (o1.getCurrentCost() < o2.getCurrentCost()) {
			return 1;
		}
		return 0;
	}

}