WuhanDijkstra

/*
 * 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 Contest;

import java.io.File;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 *
 * @author acer
 */
public class wuhanDijkstra {

    public static int [] d;
    public static int [] parent;
    public static int [] color;
    public static int [][] matrix;
    public static int node;
     public static PriorityQueue<Integer> q =new PriorityQueue<Integer>();

     public static void main(String[] args) {


        try{
            //Scanner scn=new Scanner(new File("F:\\CSE_BRACU\\Courses_TAKEN\\LABS\\Algorithm_221\\Ins.txt"));

           Scanner kb=new Scanner(System.in);

            node=kb.nextInt();

            int edge=kb.nextInt();

            matrix=new int[node][node];
            color=new int[node];
            parent=new int[node];
            d=new int[node];
            String splitA[];
            int k=0;
            while(k<edge)
            {
            //String line=kb.nextLine();
            //splitA=line.split(",");
            int x=kb.nextInt();
            int y=kb.nextInt();
            int w=kb.nextInt();
            matrix[x][y]=w;

            k++;
            }
        /* for(int i=0;i<node;i++) {
                for(int j=0;j<node;j++) {
                    System.out.print(matrix[i][j]+",");
                }
                System.out.println();
            }*/
      dijkstra(0);

        } catch (Exception ex) {
            ex.printStackTrace();
               }
     }
     public static void dijkstra(int s){
        for(int i=0;i<node;i++){
            color[i]=0;
            parent[i]=-1;
            d[i]=99999;
        }


        d[s]=0;
        color[s]=1;
        parent[s]=-1;

        q.add(d[s]);

        while(!q.isEmpty()){
            int u=findIndex(q.poll(),d);
            //System.out.println("u"+u);
            for(int v=0;v<node;v++){
                if(matrix[u][v]!=0){
                    if(color[v]==0){
                        if((d[u]+matrix[u][v])<d[v]){
                            //System.out.println("v"+v);
                            d[v]=d[u]+matrix[u][v];
                            parent[v]=u;

                        }
                    }
                }
            }
            color[u]=1;
            queueSort();

        }

        for(int i=0;i<node;i++){
            if(i!=s){
            System.out.println(d[i]);
            }

        }


     }

     public static int findIndex(int value,int [] arr) {
         int index=-1;
         for(int i=0;i<arr.length;i++){
             if(value==arr[i] ){
                 index=i;
             }
         }
        return index;
    }

      public static void queueSort(){
       q.clear();
        for(int k=0;k<node;k++){
            if(color[k]==0){
            q.add(d[k]);
            //System.out.println(d[k]);

        }

       }
          //System.out.println("queue"+q.toString());


    }


    /* public static void printPath(int node){
        int x=node;
        int sum=0;
        while(x!=-1 )
        {
            System.out.print(x+"<<-");
            sum+=d[x];
            System.out.println(d[x]);
            x=parent[x];

        }
         System.out.println("SUM"+sum);
        System.out.println();
    }*/
     }