341 - Non-Stop Travel

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

twinsister
New poster
Posts: 1
Joined: Tue Mar 06, 2012 5:50 am

Re: 341 Non-Stop Travel

Post by twinsister » Tue Mar 06, 2012 5:56 am

Have anyone figured out if the above code works?
Judge Rocks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 Non-Stop Travel

Post by brianfry713 » Tue Mar 06, 2012 10:08 pm

The code above gets WA.
Check input and AC output for thousands of problems on uDebug!

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 341 Non-Stop Travel

Post by SyFy » Wed Jun 20, 2012 11:32 pm

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. :roll:

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
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 341 Non-Stop Travel

Post by pranon » Tue Jul 24, 2012 3:45 pm

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. :(
Last edited by pranon on Tue Jul 24, 2012 11:11 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 Non-Stop Travel

Post by brianfry713 » Tue Jul 24, 2012 10:51 pm

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 - WA

Post by brianfry713 » Wed Jan 09, 2013 9:49 pm

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
Check input and AC output for thousands of problems on uDebug!

acar_go
New poster
Posts: 8
Joined: Tue Mar 11, 2014 7:33 pm

341 - WA

Post by acar_go » Tue Mar 11, 2014 7:37 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 - WA

Post by brianfry713 » Tue Mar 11, 2014 10:01 pm

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

acar_go
New poster
Posts: 8
Joined: Tue Mar 11, 2014 7:33 pm

Re: 341 - WA

Post by acar_go » Tue Mar 11, 2014 10:40 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 - WA

Post by brianfry713 » Wed Mar 12, 2014 11:38 pm

Don't print a blank line at the start of the output.
Check input and AC output for thousands of problems on uDebug!

acar_go
New poster
Posts: 8
Joined: Tue Mar 11, 2014 7:33 pm

Re: 341 - WA

Post by acar_go » Thu Mar 13, 2014 1:25 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 341 - WA

Post by brianfry713 » Fri Mar 14, 2014 1:09 am

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
Check input and AC output for thousands of problems on uDebug!

acar_go
New poster
Posts: 8
Joined: Tue Mar 11, 2014 7:33 pm

Re: 341 - WA

Post by acar_go » Sat Mar 15, 2014 4:18 pm

Finally got AC, I had an unnecessary statement.

Thank you. Happy solving!

Tanmoy Tapos Datta
New poster
Posts: 5
Joined: Mon Jul 14, 2014 10:04 pm

Re: 341 - Non-Stop Travel

Post by Tanmoy Tapos Datta » Fri Nov 14, 2014 10:02 pm

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

Code: Select all

Got AC  :D 
Last edited by Tanmoy Tapos Datta on Fri Nov 14, 2014 11:42 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 341 - Non-Stop Travel

Post by lighted » Fri Nov 14, 2014 10:39 pm

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. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 3 (300-399)”