(UVA) Sending Email - Solution

I used Dijkstra to solve this problem.

This problem is interesting because you need to check if two nodes have bidirectional edges between each other. If yes, then the cost for that operation is 0.


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

class Main {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
    public static int[][] matrixWeight;
   
    public static Comparator<Edge> weighComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return (int) e1.weight - e2.weight;
        }
    };
   
    public static int dijkstra(int start, int end, int numServers) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numServers, weighComparator);
        Edge e = new Edge(start, 0);
        queue.add(e);

        int[] visited = new int[numServers];
       
        while (queue.size() > 0) {
            Edge currEdge = queue.poll();
            int currServer = currEdge.server;
            int currWeight = currEdge.weight;
            visited[currServer] = 1;
           
            if (currServer == end) {
                return currWeight;
            }
           
            ArrayList<Edge> reachableServers = adjList.get(currServer);
            for (int i = 0; i < reachableServers.size(); i++) {
                Edge next = reachableServers.get(i);
                if (visited[next.server] == 0) {
                    int weight = next.weight;
                    e = new Edge(next.server, currWeight+weight);
                    queue.add(e);
                }
            }
        }
       
        return -1;
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numTests = reader(br);
        for (int i = 0; i < numTests; i++) {
            int numServers = reader(br);
            int numConnections = reader(br);
            int serverStart = reader(br);
            int serverEnd = reader(br);
       
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int j = 0; j < numServers; j++) {
                adjList.put(j, new ArrayList<Edge>());
            }
           
            for (int j = 0; j < numConnections; j++) {
                int s1 = reader(br);
                int s2 = reader(br);
                int weight = reader(br);
                Edge e = new Edge(s2, weight);
                adjList.get(s1).add(e);
                e = new Edge(s1, weight);
                adjList.get(s2).add(e);
            }
           
            int answer = dijkstra(serverStart, serverEnd, numServers);
           
            if (answer == -1) {
                System.out.println("Case #" + (i+1) + ": unreachable");
            }
            else {
                System.out.println("Case #" + (i+1) + ": " + answer);
            }
        }
                 
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int server;
    int weight;
   
    public Edge(int s, int w) {
        server = s;
        weight = w;
    }
}