UVA – 341 – Non-Stop Travel

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Vector;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int V = -1;
		int kase = 1;
		while ((V = in.nextInt()) != 0) {
			Dijkstra d = new Dijkstra(V);
			for (int a = 0; a < V; a++) {
				int E = in.nextInt();
				for (int i = 0; i < E; i++) {

					int b = in.nextInt() - 1;
					int w = in.nextInt();

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

			Integer[] a = d.getShortestPathFromTo(in.nextInt() - 1, in.nextInt() - 1);
			String ans = "";
			for (int i = 2; i <= 1 + a[1]; i++)
				ans += " " + a[i];
			System.out.printf("Case %d: Path =%s; %d second delay\n", kase++, ans, a[0]);
		}
	}
}

class Dijkstra {
	Integer[] distance;
	Integer[] parent;
	ArrayList<Integer>[] adj;
	Integer w[][];
	boolean[] visited;
	final int V;
	final int MAX_VALUE = 2 << 23;

	@SuppressWarnings("unchecked")
	public Dijkstra(int V_) {
		this.V = V_;
		distance = new Integer[V];
		parent = 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);
		Arrays.fill(parent, -1);
		distance[s] = 0;
	}

	/**
	 * 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);
		for (int i = 0; i < V; i++) {
			int min = minimum();
			visited[min] = true;
			relax(min);
		}

		return getPath(a, b);
	}

	private void relax(int a) {
		for (Integer b : adj[a])
			if (distance[b] > distance[a] + w[a][b]) {
				distance[b] =  distance[a] + w[a][b];
				parent[b] = a;
			}
	}

	private int minimum() {
		int min = -1;
		for (int i = 0; i < V; i++)
			if (!visited[i] && (min == -1 || distance[min] > distance[i]))
				min = i;
		return min;
	}

	private Integer[] getPath(int a, int b) {
		Vector<Integer> p = new Vector<Integer>();

		for (int cur = b; cur != a; cur = parent[cur])
			p.add(cur);
		p.add(a);
		int size = p.size();
		p.add(size);
		p.add(distance[b]);

		Collections.reverse(p);
		Integer[] path = new Integer[p.size()];
		p.toArray(path);
		return path;
	}
}
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: