Untitled

/*
To change this license header, choose License Headers in Project Properties.
To change this template file, choose Tools | Templates
and open the template in the editor.
*/

package q1;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Q1 {
    String inputFile = "dijkstra_input2.txt";
    String outputFile = "dijkstra_output2.txt";
    
    //--VARIABLES - @STUDENT: DECLARE YOUR VARIABLES HERE:
    int N, M, s, e;
    List<List<Edge>> adj;
    int[] distance;
    int[] prev;
    String result = "";
    
    //--FIXED PART - DO NOT EDIT ANY THINGS HERE--
    //--START FIXED PART--------------------------    
    String fi, fo;

    /**
     * Set input and output file for automatic rating
     * @param args path of input file and path of output file
     */
    public void setFile(String[] args) {
        fi = args.length >= 2 ? args[0] : inputFile;
        fo = args.length >= 2 ? args[1] : outputFile;
    }

    /**
     * Reads data from input file
     */
    public void read() {
        try (Scanner sc = new Scanner(new File(fi))) {
            //--END FIXED PART----------------------------

            //INPUT - @STUDENT: ADD YOUR CODE FOR INPUT HERE:
            N = sc.nextInt();
            M = sc.nextInt();
            s = sc.next().charAt(0) - 'A';
            e = sc.next().charAt(0) - 'A';
            
            adj = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                adj.add(new ArrayList<>());
            }
            
            for (int i = 0; i < M; i++) {
                int u = sc.next().charAt(0) - 'A';
                int v = sc.next().charAt(0) - 'A';
                int d = sc.nextInt();
                adj.get(u).add(new Edge(v, d));
                adj.get(v).add(new Edge(u, d));
            }
            //--FIXED PART - DO NOT EDIT ANY THINGS HERE--
            //--START FIXED PART--------------------------    
            sc.close();
        } catch (FileNotFoundException ex) {
            System.out.println("Input Exception # " + ex);
        }
    }
    //--END FIXED PART----------------------------

    //ALGORITHM - @STUDENT: ADD YOUROWN METHODS HERE (IF NEED):
    private class Edge {
        int vertex, weight;
        
        Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }
    
    private void dijkstra(int start) {
        distance = new int[N];
        prev = new int[N];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        distance[start] = 0;
        
        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        pq.add(new Edge(start, 0));
        
        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int u = current.vertex;
            int d = current.weight;
            
            if (d > distance[u]) continue;
            
            for (Edge edge : adj.get(u)) {
                int v = edge.vertex;
                int weight = edge.weight;
                
                if (distance[u] + weight < distance[v]) {
                    distance[v] = distance[u] + weight;
                    prev[v] = u;
                    pq.add(new Edge(v, distance[v]));
                }
            }
        }
    }
    
    private List<Integer> getPath(int end) {
        List<Integer> path = new ArrayList<>();
        for (int at = end; at != -1; at = prev[at]) {
            path.add(0, at);
        }
        return path;
    }

    //--FIXED PART - DO NOT EDIT ANY THINGS HERE--
    //--START FIXED PART--------------------------    
    /**
     * Main algorithm
     */
    public void solve() {
        //--END FIXED PART----------------------------

        //ALGORITHM - @STUDENT: ADD YOUR CODE FOR OUTPUT HERE:
        dijkstra(s);
        
        List<Integer> path = getPath(e);
        
        result += distance[e] + "\n";
        for (int i = 0; i < path.size(); i++) {
            result += ((char) (path.get(i) + 'A'));
            if (i < path.size() - 1) {
                result += ("->");
            }
        }
        
        //--FIXED PART - DO NOT EDIT ANY THINGS HERE--
        //--START FIXED PART-------------------------- 
    }

    /**
     * Write result into output file
     */
    public void printResult() {
        try {
            FileWriter fw = new FileWriter(fo);
            //--END FIXED PART----------------------------

            //OUTPUT - @STUDENT: ADD YOUR CODE FOR OUTPUT HERE:
            fw.write(result);

            //--FIXED PART - DO NOT EDIT ANY THINGS HERE--
            //--START FIXED PART-------------------------- 
            fw.flush();
            fw.close();
        } catch (IOException ex) {
            System.out.println("Output Exception # " + ex);
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Q1 q = new Q1();
        q.setFile(args);
        q.read();
        q.solve();
        q.printResult();
    }
    //--END FIXED PART----------------------------    
}