341 - Non-Stop Travel

[twinsister]

Have anyone figured out if the above code works?

[brianfry713]

The code above gets WA.

[SyFy]

Hello!
Can somebody provide me tricky testcases pls... I am getting WA, but checked my code many times - nothing. Checked with extra '\n', without '\n', path generation - its all ok.

Link to ideone.com code and here:

Code: Select all

got AC... dont know what was wrong... rewrote my code from scratch and AC.

[pranon]

Can anyone tell me what's wrong with my code? Or some sample i/o for which it fails?

Code: Select all

Removed after AC. Remember not to manipulate the loop counter...

Thanks in advance.

[brianfry713]

Doesn't match the sample I/O.

[brianfry713]

Input:

Code: Select all

4
2  2 1  3 2
1  4 10
1  4 1
0
1 4

0

Correct output:

Code: Select all

Case 1: Path = 1 3 4; 3 second delay

[acar_go]

Hi everybody!

WA all the time I have all the test cases that I've tried work.

Thank you.

Code: Select all

import java.util.Scanner;

public class Main {
	
	private static Scanner in;
	private double map[][];
	private int path[][];

	public void process() {
		int nNodes, nInter, aNode, init, target, nTest = 0;
		double minValor;
		while (in.hasNext()) {
			nNodes = in.nextInt();
			if (nNodes != 0) {
				nTest++;
				map = new double[nNodes][nNodes];
				path = new int[nNodes][nNodes];
				for (int i = 0; i < nNodes; i++) {
					for (int j = 0; j < nNodes; j++) {
						map[i][j] = Double.POSITIVE_INFINITY;
						path[i][j] = i;
					}
					map[i][i] = 0;
				}
				for (int i = 0; i < nNodes; i++) {
					nInter = in.nextInt();
					for (int j = 0; j < nInter; j++) {
						aNode = in.nextInt();
						if(aNode != 0)
							map[i][aNode - 1] = in.nextInt();
					}
				}
				init = in.nextInt();
				target = in.nextInt();
				
				for (int k = 0; k < nNodes; k++) {
					for (int i = 0; i < nNodes; i++) {
						for (int j = 0; j < nNodes; j++) {
							minValor = map[i][k] + map[k][j];
							if (minValor < map[i][j]) {
								map[i][j] = minValor;
								path[i][j] = k;
							}
						}
					}
				}
				System.out.print("\nCase " + nTest + ": Path = ");
				pathDisplay(init - 1, target - 1);
				System.out.print(" " + (int) map[init - 1][target - 1]
						+ " second delay");
			}else
				return;
		}
	}

	private void pathDisplay(int i, int j) {
		String track = "";
		int ant = path[i][j];
		track = (ant + 1) + " " + (j + 1) + ";";
		while (i != ant) {
			ant = path[i][ant];
			track = (ant + 1) + " " + track;
		}
		System.out.print(track);
	}

	public static void main(String[] args) throws Exception {
		in = new Scanner(System.in);
		new Main().process();
		in.close();
		return;
	}
}

[brianfry713]

Try solving it without using floating point.

[acar_go]

I still have WA

Code: Select all

import java.util.Scanner;

public class Main {
	
	private static Scanner in;
	private int map[][];
	private int path[][];

	public void process() {
		int nNodes, nInter, aNode, init, target, nTest = 0, minValor;
		boolean first = true;
		while (in.hasNext()) {
			nNodes = in.nextInt();
			if(first){
				System.out.println();
				first = false;
			}
			if (nNodes != 0) {
				nTest++;
				map = new int[nNodes][nNodes];
				path = new int[nNodes][nNodes];
				for (int i = 0; i < nNodes; i++) {
					for (int j = 0; j < nNodes; j++) {
						map[i][j] = 1000000000; //Segun CP3 use 1.10^9 to avoid overflow
						path[i][j] = i;
					}
					map[i][i] = 0;
				}
				for (int i = 0; i < nNodes; i++) {
					nInter = in.nextInt();
					for (int j = 0; j < nInter; j++) {
						aNode = in.nextInt();
						if(aNode != 0)
							map[i][aNode - 1] = in.nextInt();
					}
				}
				init = in.nextInt();
				target = in.nextInt();
				
				for (int k = 0; k < nNodes; k++) {
					for (int i = 0; i < nNodes; i++) {
						for (int j = 0; j < nNodes; j++) {
							minValor = map[i][k] + map[k][j];
							if (minValor < map[i][j]) {
								map[i][j] = minValor;
								path[i][j] = k;
							}
						}
					}
				}
				System.out.print("Case " + nTest + ": Path = ");
				pathDisplay(init - 1, target - 1);
				System.out.println(" " + map[init - 1][target - 1]
						+ " second delay");
			}
		}
	}

	private void pathDisplay(int i, int j) {
		String track = "";
		int ant = path[i][j];
		track = (ant + 1) + " " + (j + 1) + ";";
		while (i != ant) {
			ant = path[i][ant];
			track = (ant + 1) + " " + track;
		}
		System.out.print(track);
	}

	public static void main(String[] args) throws Exception {
		in = new Scanner(System.in);
		new Main().process();
		in.close();
	}
}

[brianfry713]

Don't print a blank line at the start of the output.

[acar_go]

Still not working. I'm going crazy

Code: Select all

import java.util.Scanner;

public class Main {

	private static Scanner in;
	private int map[][];
	private int path[][];

	public void process() {
		int nNodes, nInter, aNode, init, target, nTest = 0, minValor;
		while ((nNodes = in.nextInt()) != 0) {
			nTest++;
			map = new int[nNodes][nNodes];
			path = new int[nNodes][nNodes];
			for (int i = 0; i < nNodes; i++) {
				for (int j = 0; j < nNodes; j++) {
					map[i][j] = 1000000000; // Segun CP3 use 1.10^9 to avoid
											// overflow
					path[i][j] = i;
				}
				map[i][i] = 0;
			}
			for (int i = 0; i < nNodes; i++) {
				nInter = in.nextInt();
				for (int j = 0; j < nInter; j++) {
					aNode = in.nextInt();
					if (aNode != 0)
						map[i][aNode - 1] = in.nextInt();
				}
			}
			init = in.nextInt();
			target = in.nextInt();

			for (int k = 0; k < nNodes; k++) {
				for (int i = 0; i < nNodes; i++) {
					for (int j = 0; j < nNodes; j++) {
						minValor = map[i][k] + map[k][j];
						if (minValor < map[i][j]) {
							map[i][j] = minValor;
							path[i][j] = k;
						}
					}
				}
			}
			System.out.print("Case " + nTest + ": Path = ");
			pathDisplay(init - 1, target - 1);
			System.out.println(" " + map[init - 1][target - 1]
					+ " second delay");
		}
	}

	private void pathDisplay(int i, int j) {
		String track = "";
		int ant = path[i][j];
		track = (ant + 1) + " " + (j + 1) + ";";
		while (i != ant) {
			ant = path[i][ant];
			track = (ant + 1) + " " + track;
		}
		System.out.print(track);
	}

	public static void main(String[] args) throws Exception {
		in = new Scanner(System.in);
		new Main().process();
		in.close();
	}
}

I have tried many test and all work

[brianfry713]

Input:

Code: Select all

4
4  1 57  2 11  3 14  4 97
4  1 45  2 17  3 10  4 80
4  1 63  2 74  3 29  4 48
4  1 7  2 42  3 52  4 10
3 2

0

AC output:

Code: Select all

Case 1: Path = 3 4 1 2; 66 second delay

[acar_go]

Finally got AC, I had an unnecessary statement.

Thank you. Happy solving!

[Tanmoy Tapos Datta]

Getting Wrong Answer but all sample test case give the correct output....

Code: Select all

Got AC  :D 

[lighted]

Always copy/paste output format from sample or problem description.

Sample Output

Code: Select all

Case 1: Path = 2 1 4; 8 second delay

Your Output

Code: Select all

Case 1: Path = 2 1 4 ; 8 second delay

Don't forget to remove your code after getting accepted.