# UVa 544

## Summary

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

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);
}
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.remove(startNode);
startNode.setCurrentCost(Integer.MAX_VALUE);

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);
}
}
}

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 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;
}

}
```