/**
 * Sequential Version of Dijkstra's Algorithm
 */

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map;
import java.util.Collections;
import java.util.List;
import edu.rit.pj.Comm;
import edu.rit.pj.ParallelRegion;
import edu.rit.pj.ParallelTeam;
import edu.rit.pj.ParallelIteration;

public class DijkstraColSmp {

	private final static Integer infinity = 2000;
	static int len = 0;
	static Graph g;
	static Map<Vertex, Integer> distFromSource;
	static Map<Vertex, Vertex> previousNode;
	static Map<Vertex, Integer> unvisitedNodes;
	static Vertex currentNode;

	/**
	 * @param args
	 *            0 - Filename where Vertices and Edges are stored
	 * @param args
	 *            1 - Name of the source vertex
	 * @param args
	 *            2 - Name of the destination vertex
	 */
	public static void main(String[] args) throws Exception{
		Comm.init (args);
		double begin = System.currentTimeMillis();
		String fileName = null;
		Vertex source = null;
		Vertex destination = null;
		if (args.length == 3) {
			fileName = args[0];
			source = new Vertex(Integer.parseInt(args[1]));
			destination = new Vertex(Integer.parseInt(args[2]));
		} else {
			System.err.println("Invalid command-line arguements");
			System.exit(0);
		}

		List<Vertex> vertices = Collections.synchronizedList( new ArrayList<Vertex>() );
		ArrayList<Edge> edges = new ArrayList<Edge>();
		try {
			BufferedReader in = new BufferedReader(new FileReader(fileName));
			String line = in.readLine();
			len = Integer.parseInt( line );
			while ((line = in.readLine()) != null) {
				Scanner scan = new Scanner( line );
				Vertex start = new Vertex( scan.nextInt() );
				Vertex end = new Vertex( scan.nextInt() );
				if( !vertices.contains( start ) ) vertices.add( start );
				if( !vertices.contains( end ) ) vertices.add( end );
				edges.add( new Edge( start, end, scan.nextInt() ) );
			}
			in.close();
		} catch( Exception e ) {
			e.printStackTrace();
		}
		
		g = new Graph( vertices, edges );
		
		//*** Dijkstra's Algorithm ***\\
		distFromSource = new TreeMap<Vertex, Integer>();
		previousNode = new TreeMap<Vertex, Vertex>();
		unvisitedNodes = new TreeMap<Vertex, Integer>();
		for( Vertex v : g.getVertices() ) {
			distFromSource.put( v, infinity );
			previousNode.put( v, null );
			unvisitedNodes.put( v, null );
		}
		distFromSource.put(source, 0);
		
		new ParallelTeam().execute( new ParallelRegion()
            		{
            		public void run() throws Exception
			{
				for( Vertex v : unvisitedNodes.keySet() ) {
					currentNode = v;
					for( Vertex v2 : unvisitedNodes.keySet() ) {
						if( distFromSource.get( v2 ) < distFromSource.get( currentNode ) && unvisitedNodes.get( v2 ) == null )
							currentNode = v2;
					}
					unvisitedNodes.put( currentNode, new Integer( 1 ) );
					execute( g.getEdgesContaining( currentNode ), new ParallelIteration<Edge>()
                 				{
						public void run( Edge e )
                     					{
							int newDist = distFromSource.get( currentNode ) + e.getDistance();
							Vertex otherVertex = e.getOtherVertex( currentNode );
							if( newDist < distFromSource.get( otherVertex ) ) {
								distFromSource.put( otherVertex, newDist );
								previousNode.put( otherVertex, currentNode );
								}
							}
						});
					}
				}
			});
		
		Vertex prev = previousNode.get( destination );
		String output = "[" + destination.getName() + "]";
		while( !source.equals( prev ) ) {
			output = "[" + prev.getName() + "] -> " + output;
			prev = previousNode.get( prev );
		}
		output = "[" + source.getName() + "] -> " + output + " (Total Distance = " + distFromSource.get( destination ) + ")";
		System.out.println( output );
		double end = System.currentTimeMillis();
		System.out.println("Runing time: "+ (end - begin));
	}

}