1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 11710 - Expensive subway
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2757
*
* @author Christian Posselt
* @author Christian Mitterreiter
* @version 1.0, 18.05.2011
*
* Status:
* Time:
*/

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main
{

public static void main(String[] args)
{
Scanner sc = new Scanner(new InputStreamReader(System.in));
ArrayList<Integer> answers = new ArrayList<Integer>();

do
{
//first line tells how many knots the tree has
int vertices = sc.nextInt();
int edges = sc.nextInt();

if(vertices == 0 && edges == 0)
break;

ArrayList<String> stations = new ArrayList<String>();

//read in the coordinates
for(int i=0;i<vertices;i++)
{
stations.add(sc.next());
}


//create an empty MST
Kruskal result = new Kruskal(vertices);

//read in the given edges
for(int i=0;i<edges;i++)
{
int verticeA = stations.indexOf(sc.next());
int verticeB = stations.indexOf(sc.next());

result.addEdge(verticeA, verticeB, sc.nextInt());
}

sc.next();

//calculate the MST with the given edges
Object[] tree = result.minimalSpannTree();

int weight = (Integer) tree[0];

//save weight without the amount of existing Cables
answers.add(weight);

}
while(true);

//print all results. No line break at the end.
for(int i=0;i<answers.size();i++)
{
if(i<answers.size()-1)
if(answers.get(i) == -1)
System.out.println("Impossible");
else
System.out.println(answers.get(i));
else
if(answers.get(i) == -1)
System.out.print("Impossible");
else
System.out.println(answers.get(i));

}
}

/**
* Inner Class to solve the MST
* with Kruskal Algorithm
*
*/
static class Kruskal
{
/**
* Edges.
* Double[0] - Point A
* Double[1] - Point B
* Double[2] - Distance
*/
private final PriorityQueue<Integer[]> edges;

/**
* Amount of Points
*/
private final int vertices;

/**
* Weight of the MST
*/
private int weight;

/**
* Amount of Edges Selected
*/
private int selectedEdges;

/**
* Components
*/
private int[] ways;

Kruskal(int vertices)
{
this.vertices = vertices;

//Use a priority Queue to sort the edges according to the shortest distance
edges = new PriorityQueue<Integer[]>(vertices,new Comparator<Integer[]>(){
public int compare(Integer[] a, Integer[] b)
{
double aw = a[2];
double bw = b[2];
if (aw==bw)return 0;
if (aw<bw)return -1;
return 1;
}
});
}

//add edge to Priority Queue
public void addEdge(int x, int y, int weight)
{
edges.add(new Integer[]{x,y,weight});
}

//returns the first element in the queue
public Integer[] getEdge()
{
return edges.poll();
}

/**
*
* @param required - List of Edges which are given
* @return Object[0] - double: weight of MST
* Object[1] - Kruskal: MST
*
*/
public Object[] minimalSpannTree()
{

try
{
Kruskal minimal = new Kruskal(vertices);

weight = 0;
selectedEdges = 0;


ways = new int[vertices];

//initializing components
for(int i=0;i<vertices;i++)
ways[i] = i;

//find the smallest edges to form the MST
while(selectedEdges < vertices-1)
{
Integer[] edge = null;


do
{
edge = this.getEdge();
}
//make sure the edge does not form a circle
while(ways[edge[0].intValue()] == ways[edge[1].intValue()]);

weight += edge[2];
selectedEdges++;

minimal.addEdge(edge[0],edge[1],edge[2]);

int max = Math.max(edge[0].intValue(), edge[1].intValue());
int min = Math.min(edge[0].intValue(), edge[1].intValue());

//unify the component
for(int i=0;i<vertices;i++)
if(ways[i] == max)
ways[i] = min;

}

return new Object[]{weight, minimal};
}
catch(NullPointerException e)
{
return new Object[]{-1, null};
}
}
}


}

----------------------------------------------

1.

package graphs.mst.expensiveSubway;
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 11710 Expensive Subways
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2757
*
* @author Patrick Bédat
* @version 1.0, 14.11.2010
*
* Method : Prim
* Status : Accepted
* Runtime: 3.396
*/
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.*;

class Main {

static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

public static void main(String[] agrs) throws IOException {
int nVerticies;
int nEdges;

do {
StringTokenizer st = new StringTokenizer(reader.readLine());
if(!st.hasMoreTokens())
break;
nVerticies = Integer.parseInt(st.nextToken());
nEdges = Integer.parseInt(st.nextToken());

if (nVerticies == 0) {
break;
}

HashMap<String, Integer> mapStationID = new HashMap<String, Integer>();
HashMap<Integer, HashSet<Edge>> neighbourEdges = new HashMap<Integer, HashSet<Edge>>();

for (int i = 0; i < nVerticies; i++) {
mapStationID.put(reader.readLine().trim(), i);
}

for (int i = 0; i < nEdges; i++) {
st = new StringTokenizer(reader.readLine());

String from = st.nextToken();
String to = st.nextToken();
int cost = Integer.parseInt(st.nextToken());

Edge e = new Edge(mapStationID.get(from), mapStationID.get(to), cost);

HashSet<Edge> neighboursFrom = neighbourEdges.get(e.from);

if (neighboursFrom == null) {
neighboursFrom = new HashSet<Edge>();
neighbourEdges.put(e.from, neighboursFrom);
}

HashSet<Edge> neighboursTo = neighbourEdges.get(e.to);

if (neighboursTo == null) {
neighboursTo = new HashSet<Edge>();
neighbourEdges.put(e.to, neighboursTo);
}

neighboursFrom.add(e);
neighboursTo.add(e);
}

//start
String startName = reader.readLine().trim();

if(!mapStationID.containsKey(startName))
{
System.out.println("Impossible");
continue;
}
int start = mapStationID.get(startName);

HashSet<Integer> newGraphVerticies = new HashSet<Integer>();
newGraphVerticies.add(start);

PriorityQueue<Edge> stack = new PriorityQueue<Edge>();

if(nVerticies == 1)
{
System.out.println("0");
continue;
}

if(neighbourEdges.get(start) == null)
{
System.out.println("Impossible");
continue;
}

for (Edge n : neighbourEdges.get(start)) {
stack.add(n);
}

int totalCost = 0;

while (newGraphVerticies.size() < nVerticies && !stack.isEmpty()) {
Edge current = stack.poll();

if (!newGraphVerticies.contains(current.from)) {
totalCost += current.cost;

for (Edge n : neighbourEdges.get(current.from)) {
if (!newGraphVerticies.contains(n.from) || !newGraphVerticies.contains(n.to)) {
stack.add(n);
}
}

newGraphVerticies.add(current.from);
} else if (!newGraphVerticies.contains(current.to)) {
totalCost += current.cost;
for (Edge n : neighbourEdges.get(current.to)) {
if (!newGraphVerticies.contains(n.from) || !newGraphVerticies.contains(n.to)) {
stack.add(n);
}
}
newGraphVerticies.add(current.to);
}
}

if (newGraphVerticies.size() < nVerticies) {
System.out.println("Impossible");
} else {
System.out.println(totalCost);
}

} while (reader.ready());
}

static class Edge implements Comparable<Edge> {

int from;
int to;
int cost;

public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}

public int compareTo(Edge o) {
if (cost < o.cost) {
return -1;
}
if (cost > o.cost) {
return 1;
}
return 0;
}

@Override
public int hashCode() {
return Math.min(from, to) + Math.max(from, to) * 1000;
}

@Override
public boolean equals(Object o) {
return hashCode() == o.hashCode();
}
}
}