341 - Non-Stop Travel
Moderator: Board moderators
-
- New poster
- Posts: 1
- Joined: Tue Mar 06, 2012 5:50 am
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 Non-Stop Travel
The code above gets WA.
Check input and AC output for thousands of problems on uDebug!
Re: 341 Non-Stop Travel
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:
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:](./images/smilies/icon_rolleyes.gif)
Link to ideone.com code and here:
Code: Select all
got AC... dont know what was wrong... rewrote my code from scratch and AC.
Re: 341 Non-Stop Travel
Can anyone tell me what's wrong with my code? Or some sample i/o for which it fails?
Thanks in advance. ![:(](./images/smilies/icon_frown.gif)
Code: Select all
Removed after AC. Remember not to manipulate the loop counter...
![:(](./images/smilies/icon_frown.gif)
Last edited by pranon on Tue Jul 24, 2012 11:11 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 Non-Stop Travel
Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 - WA
Input:Correct output:
Code: Select all
4
2 2 1 3 2
1 4 10
1 4 1
0
1 4
0
Code: Select all
Case 1: Path = 1 3 4; 3 second delay
Check input and AC output for thousands of problems on uDebug!
341 - WA
Hi everybody!
WA all the time I have all the test cases that I've tried work.
Thank you.
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;
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 - WA
Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!
Re: 341 - WA
I still have WA ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
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();
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 - WA
Don't print a blank line at the start of the output.
Check input and AC output for thousands of problems on uDebug!
Re: 341 - WA
Still not working. I'm going crazy
I have tried many test and all work ![:(](./images/smilies/icon_frown.gif)
![:-?](./images/smilies/icon_confused.gif)
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();
}
}
![:(](./images/smilies/icon_frown.gif)
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 341 - WA
Input:AC output:
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
Code: Select all
Case 1: Path = 3 4 1 2; 66 second delay
Check input and AC output for thousands of problems on uDebug!
Re: 341 - WA
Finally got AC, I had an unnecessary statement.
Thank you. Happy solving!
Thank you. Happy solving!
-
- New poster
- Posts: 5
- Joined: Mon Jul 14, 2014 10:04 pm
Re: 341 - Non-Stop Travel
Last edited by Tanmoy Tapos Datta on Fri Nov 14, 2014 11:42 pm, edited 1 time in total.
Re: 341 - Non-Stop Travel
Always copy/paste output format from sample or problem description. ![:)](./images/smilies/icon_smile.gif)
Sample OutputYour Output
Don't forget to remove your code after getting accepted. ![8)](./images/smilies/icon_cool.gif)
![:)](./images/smilies/icon_smile.gif)
Sample Output
Code: Select all
Case 1: Path = 2 1 4; 8 second delay
Code: Select all
Case 1: Path = 2 1 4 ; 8 second delay
![8)](./images/smilies/icon_cool.gif)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman