UVA – 558 – Wormholes

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;



public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int T = in.nextInt();

		while (T-- != 0) {

			int V = in.nextInt(), E = in.nextInt();

			BellmanFord b = new BellmanFord(V);

			for (int i = 0; i < E; i++)

				b.addEdge(in.nextInt(), in.nextInt(), in.nextInt());



			boolean traveledBack = false;

				if (!b.solve(0)) {

					traveledBack = true;

				}

				



			if (traveledBack)

				System.out.println("possible");

			else

				System.out.println("not possible");

		}

	}

}



class BellmanFord {



	Integer[] distance;

	Integer[] parent;

	ArrayList<Edge> edges;



	/** Constructor Takes The No. of Vertices */

	public BellmanFord(int V) {

		distance = new Integer[V];

		parent = new Integer[V];

		edges = new ArrayList<Edge>(3 * V);

	}



	public void addEdge(int a, int b, int w) {

		edges.add(new Edge(a, b, w));

	}



	public boolean solve(Integer source) {

		initFromSource(source);

		for (int i = 0; i < distance.length; i++)

			for (Edge e : edges)

				relax(e);



		for (Edge e : edges)

			if (relax(e))

				return false;



		return true;

	}



	public Integer[] getShortestPathFromTo(int a, int b) {

		if (!solve(a))

			return null;



		ArrayList<Integer> path = new ArrayList<Integer>(distance.length);

		int i = b;



		while (parent[i] != -1) {

			path.add(i);

			i = parent[i];

		}

		Integer[] Path = new Integer[path.size()];

		path.toArray(Path);

		return Path;

	}



	public void initFromSource(Integer source) {

		Arrays.fill(distance, Integer.MAX_VALUE);

		Arrays.fill(parent, -1);

		distance = 0;

	}



	public boolean relax(Edge e) {

		if (distance[e.b] > distance[e.a] + e.w) {

			distance[e.b] = distance[e.a] + e.w;

			parent[e.b] = e.a;

			return true;

		}

		return false;

	}



}



class Edge implements Comparable<Edge> {

	int a;

	int b;

	int w;



	public Edge(int from, int to, int wi) {

		a = from;

		b = to;

		w = wi;

	}



	@Override

	public int compareTo(Edge e) {

		return this.w - e.w;

	}



}



Advertisements

One thought on “UVA – 558 – Wormholes

  1. Justin Bieber says:

    distance1 = 0 <- Variable does not exist

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: