1

I was looking through some old contest questions, and I found this one, it looked fun, http://dwite.ca/old/Problem5Jan2006.pdf , I tried using the floyd warshall algorithm to get the shortest path from any node to any other node, can you guys see what I did wrong? it does not give the desired output set out on the contest question page

import java.io.*;
import java.util.*;

public class DistanceBetween {


public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("DATA5.txt"));
    int n = Integer.parseInt(s.nextLine());
    int[][] dist = new int[60][60];
    for(int y=0;y<60;++y)for(int x=0;x<60;++x)dist[y][x]=10000000;
    Map<Character, Integer> map = new TreeMap<Character, Integer>();
    for (int i = 0; i < n; ++i) {
        String text[] = s.nextLine().split(" ");
        int c = 0;
        if (!map.containsKey(text[0].charAt(0))) {
            map.put(text[0].charAt(0), c);
            c++;
        }
        if (!map.containsKey(text[0].charAt(1))) {
            map.put(text[0].charAt(1), c);
            c++;
        }
        dist[map.get(text[0].charAt(0))][map.get(text[0].charAt(1))] = Integer.parseInt(text[1]);
    }
    for (int k = 0; k < map.size(); ++k) {
        for (int i = 0; i < map.size(); ++i) {
            for (int j = 0; j < map.size(); ++j) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        String text = s.nextLine();
        System.out.println(dist[map.get(text.charAt(0))][map.get(text.charAt(1))]);
    }
}}
2
  • it does not give the shortest path which is the output on the link Mar 21, 2013 at 6:24
  • I think it might be better that you append the specific part of your result and the result on the website that differ to your question - if that isn't too much text. Mar 21, 2013 at 8:01

2 Answers 2

2

There are several problems in your code:

Overwritten mapping

Your int c is local variable of the for cycle which means the highest used mapping index doesn't survive to the next iteration, so the reading in next iteration overrides the previous one. So the distance matrix is not properly filled after data loading.

Solution: move the int c = 0; outside from the for loop.

Unidirectional roads

The roads are bidirectional in the instructions, but you register them only as unidirectional. As the consequence of that are higher on non-existent connections between towns.

Solution: add dist[map.get(text[0].charAt(1))][map.get(text[0].charAt(0))] = Integer.parseInt(text[1]); right after the similar one.


Besides these hard issues I have also couple hints for you. You do not have follow them but as if you want to improve your programming skills then you should think about them.

Messy code

Your code is hard to read, there are multiple restated information such as indicies, the solving process is in the single method etc. Such code is not only hard to read but also extremely hard to debug and fix. For your own good I recommend you to write it cleaner.

Algorithm efficiency

Floyd-Warshall's algorithm has a O(n^3) complexity. The size of problem (amount of towns) is A-M = 13. In this complexity it makes 13^3 = 2197 iterations. I know, it might not seem to be a lot, but consider the amount of tasks to solve in a given time limit.

I would recommend you to use Dijkstra's algorithm which has complexity O(|E| + |V|log|V|). In this task the worst case with some simplification is |E| = (|V|^2)/2, |V|=13. It means, that the final number of iterations is 5 (|V|^2 / 2 + |V|log|V|) = 5 (13^2 / 2 + 13 * log13) ~ 5 * 132 = 660. If I am not wrong and made any mistake, this is significantly less, especially when we consider the total amount of tasks.

Input reading

I might be wrong but I attended multiple programming contests and competitions and it never forced attendees to work with files. An input was always redirected from files to a standard input. I guess, that the main reason for this is a security, but the simplification is probably also highly beneficial.

2
  • Well I am aware that my code is messy, and since I am going to be doing another programming contest soon, I was timing myself and finishing the code as quickly as possible, just because it is messy doesn't mean it won't work, and the judges do not mark how well your code is written only if the output matches. But anyway thanks for the advice on how to make debugging faster, anyway I haven't learned dijkstra yet but I am working on it now Mar 21, 2013 at 13:36
  • 1
    @Panphobia Yeah, I know, that judges don't care about code quality, but based on my own experience only rarely you code it working on the first attempt and then find the bug is really challenge because of the time pressure ... anyway I found your bugs and made the solution working so feel free to verify it and accept the answer if you will
    – Gaim
    Mar 21, 2013 at 14:56
0

Well that question I got, I am starting to do SPOJ now, and I gotta admit it is pretty difficult later on, but I came across the same kind of question http://www.spoj.com/problems/SHPATH/ , I also used Floyd Warshall

    import java.util.*;

    public class Floydwarshall {


public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    String q = s.nextLine();
    for(int t=0;t<Integer.parseInt(q);++t){
        int n = Integer.parseInt(s.nextLine());
        int[][] cost = new int[n][n];
        for (int y = 0; y < n; ++y) {
            for (int x = 0; x < n; ++x) {
                cost[x][y] = 10000;
            }
        }
        Map<String, Integer> map = new TreeMap<String, Integer>();
        int c = 0;
        for (int i = 0; i < n; ++i) {
            String a = s.nextLine();
            if (!map.containsKey(a)) {
                map.put(a, c);
                c++;
            }
            int f = Integer.parseInt(s.nextLine());
            for (int j = 0; j < f; ++j) {
                String text[] = s.nextLine().split(" ");
                cost[map.get(a)][Integer.parseInt(text[0]) - 1] =
                        cost[Integer.parseInt(text[0]) - 1][map.get(a)] = Integer.parseInt(text[1]);
            }
        }
        for (int k = 0; k < map.size(); ++k) {
            for (int i = 0; i < map.size(); ++i) {
                for (int j = 0; j < map.size(); ++j) {
                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        int num = Integer.parseInt(s.nextLine());
        for (int i = 0; i < num; ++i) {
            String text[] = s.nextLine().split(" ");
            System.out.println(cost[map.get(text[0])][map.get(text[1])]);
        }
    }
}}

now it runs alright for the sample input, but when I hand it in, it gives me this

NZEC (non-zero exit code) - this message means that the program exited returning a value different from 0 to the shell. For languages such as C, this probably means you forgot to add "return 0" at the end of the program. For interpreted languages (including JAVA) NZEC will usually mean that your program either crashed or raised an uncaught exception. Problem is I cannot kind where it crashes or raises an uncaught exception since it
works with the sample input

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.