UVA – 10986 – Sending email

import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Vector;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		final int MAX_VALUE = 2 << 23;
		int V = -1;
		int kase = 1;
		
		int T =  in.nextInt();
		
		while (T-- != 0) {
			
			int N = in.nextInt(), E = in.nextInt(), S = in.nextInt(), F = in.nextInt();
			Dijkstra d = new Dijkstra(N);
			for (int e = 0; e < E; e++) {
				
				int a = in.nextInt();
				int b = in.nextInt();

				int w = in.nextInt();

				d.addEdge(a, b, w);
				d.addEdge(b, a, w);
			}

			Integer[] a = d.getShortestPathFromTo(S, F);
			System.out.printf("Case #%d: " + (a[0] == MAX_VALUE ? "unreachable" : a[0]) + "\n", kase++);
		}
	}
}

class Dijkstra {
	Integer[] distance;
	ArrayList<Integer>[] adj;
	Integer w[][];
	boolean[] visited;
	final int V;
	final int MAX_VALUE = 2 << 23;
	PriorityQueue<Node> que = new PriorityQueue<Node>();

	@SuppressWarnings("unchecked")
	public Dijkstra(int V_) {
		this.V = V_;
		distance = new Integer[V];
		adj = new ArrayList[V];
		w = new Integer[V][V];
		visited = new  boolean[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<Integer>();
	}

	public void addEdge(int a, int b, int W) {
		adj[a].add(b);
		w[a][b] = W;
	}

	public void initSource(int s) {
		Arrays.fill(distance, MAX_VALUE);
		distance[s] = 0;
		
			que.add(new Node(s, distance[s]));
		
	}

	/**
	 * returns an array that is segmented as follows a[0] = the shortest path
	 * weight, a[1] = length of the wieght, a[2] -> a[a.length-1] the path
	 */
	public Integer[] getShortestPathFromTo(int a, int b) {
		initSource(a);
		while(!que.isEmpty()) {
			Node min = que.poll();
			relax(min);
		}
		return new Integer[] { distance[b]};
	}

	private void relax(Node n) {
		int a = n.x;
		for (Integer b : adj[a])
			if (!visited[b] && distance[b] > distance[a] + w[a][b]) {
				distance[b] = distance[a] + w[a][b];
				que.add(new Node(b,distance[b]));
			}
	}
}
class Node implements Comparable<Node>{
	int x;
	int d;
	public Node(int X, int D){
		this.x =X;
		this.d = D;
	}
	@Override
	public int compareTo(Node o) {
		return this.d - o.d;
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: