1.

import java.io.*;
import java.util.*;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: 10986 - Sending email
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=1927
 * 
 * @author Siegfried Ippisch
 * @author Martin Lambeck
 * @version 1.0
 * 
 * Method : Dijkstra's algorithm
 * Status : Accepted
 * Runtime: 2.380
 */
public class SendingEmail {
	
	static class Edge
	{
		Node to;
		int cost;
		
		Edge(Node t, int c)
		{
			to = t;
			cost = c;
		}
	}
	
	static class Node implements Comparable<Node>{
		LinkedList<Edge> edges = 	new LinkedList<Edge>();
		
		long value = Long.MAX_VALUE;
		boolean visited = false;
		

		@Override
		public int compareTo(Node o) {
			if (value == o.value)
				return 0;
			
			return (value < o.value ? -1 : 1);
		}
	}
	
	static long minDist(Node[] nodes, int s, int t){
		PriorityQueue<Node> a = new PriorityQueue<Node>();
		Node start = nodes[s];
		Node end = nodes[t];
		
		start.value = 0;
		a.add(start);
		
		while(!a.isEmpty())
		{
			Node n = a.poll();
			
			if (n == end)
				break;
			
			if (n.visited)
				continue;
			
			n.visited = true;
			
			for(Edge e: n.edges)
			{
				Node other = e.to;
				int cost = e.cost;
				
				if ((n.value + cost) <= other.value)
				{
					other.value = n.value + cost;
					a.add(other);
				}
			}
		}
		
		return end.value;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tests = Integer.parseInt(in.readLine());
		
		for(int c = 1; c<=tests; c++){
			String[] line = in.readLine().split(" ");
			int n = Integer.parseInt(line[0]);
			int m = Integer.parseInt(line[1]);
			int s = Integer.parseInt(line[2]);
			int t = Integer.parseInt(line[3]);
			
			// Array anlegen
			Node[] nodes = new Node[n];
			for(int i=0; i<n; i++){
				nodes[i] = new Node();
			}
			
			// Connects einlesen
			for(int i=0; i<m; i++){
				String[] l = in.readLine().split(" ");
				
				int fr = Integer.parseInt(l[0]);
				int to = Integer.parseInt(l[1]);
				int co = Integer.parseInt(l[2]);
				
				nodes[fr].edges.add(new Edge(nodes[to], co));
				nodes[to].edges.add(new Edge(nodes[fr], co));
			}
			
			// Ausgabe
			long res = minDist(nodes,s,t);
			
			if (res == Long.MAX_VALUE)
				System.out.printf("Case #%d: unreachable%n", c);
			else
				System.out.printf("Case #%d: %d%n", c, res);
		

		}
		
		in.close();
	}
	
}

2.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest 
 * Problem:     10986 - Sending email
 * Link:        http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1927
 * 
 *
 * Method :     dijkstra
 * Status :     Accepted
 * Runtime:     1.144
 *
 *
 * @author      Evgeni Pavlidis 
 * @author      Felix Dietrich
 * @version     1.0, 31/10/2010
 */

import java.io.*;
import java.util.*;

class Vertex implements Comparable<Vertex>
{
    int n, d;
    Set<Integer> edges;

    Vertex(int n)
    {
        this.n = n; 
        edges = new HashSet<Integer>();
    }

    public int compareTo(Vertex o)
    {
        if(d > o.d)
            return 1;

        if(d < o.d)
            return -1;

        return 0;
    }

    public int hashCode()
    {   return n;    }

    public boolean equals(Object o)
    {   return ((Vertex)o).n == n;    }

    public String toString()
    {
        return n + ":" + d;
    }
}

class Main
{
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int nextInt() throws IOException
    {
        st.nextToken();
        return (int)st.nval;
    }



    static final int MAX_VERTICES = 20000;
    static final int MAX_EDGES = 50000;

    static Vertex[] vertices = new Vertex[MAX_VERTICES];
    static PriorityQueue<Vertex> q = new PriorityQueue<Vertex>(MAX_VERTICES);
    static Set<Integer> used = new HashSet<Integer>(MAX_VERTICES);
    static int n,m,s,t;



    static int dijkstra()
    {
        for(int i = 0; i < n; i++)
            vertices[i].d = Integer.MAX_VALUE;
        vertices[s].d = 0;

        q.clear();
        used.clear();
        q.offer(vertices[s]);

        Vertex v;
        int w, u;

    
        while(!q.isEmpty())
        {
            v = q.poll();

            if(used.contains(v.n))
                continue;

            used.add(v.n);

            if(v.n == t)
                return v.d;

            if(v.d == Integer.MAX_VALUE)
                return Integer.MAX_VALUE;

            for(int edge: v.edges)
            {
                u = edge & 0x7FFF;

                if(!used.contains(u))
                {
                    w = v.d + (edge >> 15);
                    if(w < vertices[u].d)
                    {
                        vertices[u].d = w;
                        q.offer(vertices[u]);
                    }
                }
            }
        }

        return vertices[t].d;
    }

    public static void main(String...args) throws IOException
    {
        StringBuffer output = new StringBuffer();

        int testCases = nextInt();
        int a,b,w;

        for(int i = 0; i < MAX_VERTICES; i++)
            vertices[i] = new Vertex(i);

        for(int tc = 1; tc <= testCases; tc++)
        {
            n = nextInt();
            m = nextInt();
            s = nextInt();
            t = nextInt();

            for(int i = 0; i < n; i++)
                vertices[i].edges.clear();

            for(int i = 0; i < m; i++)
            {
                a = nextInt();
                b = nextInt();
                w = nextInt();

                vertices[a].edges.add((w<<15) + b);
                vertices[b].edges.add((w<<15) + a);
            }

            int result = dijkstra();
            output.append(String.format("Case #%d: %s\n", tc, (result == Integer.MAX_VALUE? "unreachable" : "" + result)));
        }       

        System.out.print(output);
    }
}

3.

package sendingEmail;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 10986  Sending Email
 * Link: http://uva.onlinejudge.org/external/109/10986.pdf
 *
 * @author Patrick Bédat
 * @version 1.0, 12/11/2010
 *
 * Method : Dijkstra
 * Status : Accepted
 * Runtime: 2.152
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main
{

	static Integer[] pathCost;

	public static void main(String... args) throws IOException
	{
		StringBuilder sb = new StringBuilder();

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int nTestCases = Integer.parseInt(reader.readLine());

		for (int tc = 1; tc <= nTestCases; tc++)
		{
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int nNodes = Integer.parseInt(st.nextToken());
			int nCables = Integer.parseInt(st.nextToken());
			Node startNode = new Node(Integer.parseInt(st.nextToken()), nNodes);
			Node targetNode = new Node(Integer.parseInt(st.nextToken()), nNodes);

			Node[] nodes = new Node[nNodes];

			pathCost = new Integer[nNodes];
			pathCost[startNode.id] = 0;

			for (int i = 0; i < nNodes; i++)
			{
				nodes[i] = new Node(i, nNodes);
			}

			for (int i = 0; i < nCables; i++)
			{
				st = new StringTokenizer(reader.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());

				Node fromNode = nodes[from];
				Node toNode = nodes[to];

				fromNode.connect(toNode, cost);
			}

			PriorityQueue<Node> stack = new PriorityQueue<Node>(nNodes, new NodeComp());
			stack.add(nodes[startNode.id]);

			boolean foundPath = false;

			while (!stack.isEmpty())
			{
				Node current = stack.poll();

				if (current.id == targetNode.id)
				{
					break;
				}

				for (Node neighbour : current.neighbours)
				{
					Integer costToNeighbour = pathCost[neighbour.id];
					Integer neighbourPathCost = current.costs.get(neighbour.id);
					Integer currentCost = pathCost[current.id];

					if (costToNeighbour == null || currentCost + neighbourPathCost < costToNeighbour)
					{
						pathCost[neighbour.id] = currentCost + neighbourPathCost;
						stack.add(neighbour);
					}
				}
			}

			if (pathCost[targetNode.id] != null)
			{
				sb.append("Case #").append(tc).append(": ").append(pathCost[targetNode.id]).append("\n");
			} else
			{
				sb.append("Case #").append(tc).append(": unreachable\n");
			}
		}
		System.out.print(sb);


	}

	static class Node
	{

		public int id;
		public HashMap<Integer, Integer> costs = new HashMap<Integer, Integer>();
		public LinkedList<Node> neighbours = new LinkedList<Node>();

		public Node(int id, int maxNodes)
		{
			this.id = id;
		}

		public void connect(Node neighbour, int cost)
		{
			costs.put(neighbour.id, cost);
			neighbours.add(neighbour);

			neighbour.costs.put(id, cost);
			neighbour.neighbours.add(this);
		}
	}

	static class NodeComp implements Comparator<Node>
	{
		public int compare(Node o1, Node o2)
		{
			if(pathCost[o1.id] < pathCost[o2.id])
				return -1;
			return 1;
		}
	}
}