package test;

import java.util.Random;

class Generator implements Runnable {
	private final String id;
	private static final Random RND = new Random();
	private static final int MAX_VALUE = 1000;
	public static final int COUNT = 30;
	private double[] result = new double[COUNT + 1];
	public Generator(String id) {
		this.id = id;
	}
	public long task() {
		return RND.nextInt(MAX_VALUE + 1);
	}
	@Override
	public void run() {
		result[0] = 0;
		for (int i = 0; i < COUNT; i++) {
			result[i + 1] = task();
			result[0] += result[i + 1];
		}
		result[0] /= COUNT;
		/* disp */
		double disp = 0;
		for (int i = 0; i < COUNT; i++) {
			double pt = result[i+1] - result[0];
			disp += pt * pt;
		}
		disp /= (COUNT - 1);
		System.out.println(id + "(AVG: " + result[0] + "; DISP: " + disp + ")");
	}
	public double getAvg() {
		return result[0];
	}
	public double[] getResult() {
		return result;
	}
}

class Matrix {
	public static final int[][] MTX = {
		{0, 0, 0, 0, 0, 0, 0},
		{6, 0, 0, 0, 0, 0, 0},
		{4, 0, 0, 0, 0, 0, 0},
		{0, 0, 7, 0, 0, 0, 0},
		{0, 3, 0, 0, 0, 0, 0},
		{0, 0, 0, 4, 5, 0, 0},
		{0, 0, 0, 0, 0, 3, 0}
	};
	public static final int N = MTX.length;
	public static final double MIN = -10000;
	public static final double MAX = 10000;
	private Double[][] dist;
	private Integer[][] next;
	public void fill(double inf) {
		dist = new Double[N][N];
		next = new Integer[N][N];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				dist[i][j] = inf;
	}
	public void printArray(Number[][] arr) {
		for (Number[] line : arr) {
			for (Number el : line) {
				System.out.print(el + " ");
			}
			System.out.println();
		}
	}
	public void print() {
		System.out.println("DIST:");
		printArray(dist);

		System.out.println("NEXT: ");
		printArray(next);
	}
	public String criticalPath(double[] data) {
		fill(MIN);
		int pos = 0;
		for (int u = 0; u < N; u++) {
			for (int v = 0; v < N; v++) {
				if (MTX[u][v] > 0) {
					dist[u][v] = data[pos];
					pos++;
					next[u][v] = v;
				}
			}
		}

		for (int k = 0; k < N; k++)
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					if (dist[i][k] + dist[k][j] > dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						next[i][j] = next[i][k];
					}
		return path(N - 1, 0);
	}
	public String fastestPath(double[] data) {
		fill(MAX);
		int pos = 0;
		for (int u = 0; u < N; u++) {
			for (int v = 0; v < N; v++) {
				if (MTX[u][v] > 0) {
					dist[u][v] = data[pos];
					pos++;
					next[u][v] = v;
				}
			}
		}

		for (int k = 0; k < N; k++)
			for (int i = 0; i < N; i++)
				for (int j = 0; j < N; j++)
					if (dist[i][k] + dist[k][j] < dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						next[i][j] = next[i][k];
					}
		return path(N - 1, 0);
	}
	public String path(int u, int v) {
	   String result = "";
	   if (next[u][v] == null) {
		   return result;
	   }
	   result += u + " ";
	   while (u != v) {
	       u = next[u][v];
	       result += u + " ";
	   }
	   return result;

	}
}

class Task {
	private double[][] results;
	private static final Matrix MTX = new Matrix();

	public Task(Generator[] generators) {
		results = new double[generators.length][];
		for (int i = 0; i < generators.length; i++) {
			results[i] = generators[i].getResult();
		}
	}

	public void perform() {
		String[] paths = new String[Generator.COUNT + 1];
		for (int i = 0; i < Generator.COUNT + 1; i++) {
			double[] data = new double[Matrix.N];
			for (int j = 0; j < Matrix.N; j++) {
				data[j] = results[j][i];
				if (i == 0) {
					paths[i] = MTX.criticalPath(data);
				} else {
					paths[i] = MTX.fastestPath(data);
				}
			}
		}
		int counter = 0;
		String criticalPath = paths[0];
		for (String path : paths) {
			if (criticalPath.equals(path)) {
				counter++;
			}
		}
		System.out.println("CRITICAL PATH CHANCE: " + (double)counter / Generator.COUNT * 100);
	}


}


class Runner {

	public static void main(String[] args) throws InterruptedException {
		/*Matrix m = new  Matrix();
		m.floyd();
		m.path(6, 0);*/
		Generator[] generators = new Generator[Matrix.N];
		Thread[] threads = new Thread[Matrix.N];
		for (int i = 0; i < Matrix.N; i++ ) {
			generators[i] = new Generator ("THREAD " + i);
			threads[i] = new Thread(generators[i]);
			threads[i].start();
		}

		for (Thread thread : threads) {
			thread.join();
		}

		new Task(generators).perform();
	}
}