dijkstra_adjacencyList_2020

/*
 * 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.util.LinkedList;
import java.util.Scanner;

/**
 *
3 5
0 1 10
1 2 10
2 1 100
2 0 200
1 0 300
 * @author acer
 */
public class dijkstra {
    public static int [] d;
    public static int [] parent;
     public static int [] color;
     public static int node;
     public static int edge;
     public static LinkedList[]l;

     public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
         node=sc.nextInt();
         edge=sc.nextInt();

         l=new LinkedList[node];

        for(int i=0;i<node;i++)
            l[i]=new LinkedList<String>();

        for(int i=0;i<edge;i++){
            int x=sc.nextInt();
            int y=sc.nextInt();
            int w=sc.nextInt();
            l[x].add(y+","+w);
        }

        for(int i=0;i<node;i++){
            System.out.println(i+"==>");
            for(int j=0;j<l[i].size();j++){
                System.out.println(l[i].get(j).toString());
            }
        }
       int [] d1=new int[node];
       d1=dijkstra(0);
         System.out.println();
       for(int k:d1){
           System.out.println(k);
       }

    }
     public static int[] dijkstra(int s) {
         int [] d=new int[node];
         parent=new int[node];
         color=new int[node];

         for(int i=0;i<node;i++){
             d[i]=Integer.MAX_VALUE;
             parent[i]=-1;
             color[s]=0;
         }
         d[s]=0;
         //color[s]=1;

         for(int i=0;i<node;i++){
             int u=extractMin(d);
               for(int v=0;v<l[u].size();v++){
                 String [] splitA;
                 String str=l[u].get(v).toString();
                 splitA=str.split(",");

                 int to=Integer.parseInt(splitA[0]);
                 int dist=Integer.parseInt(splitA[1]);
                 if(color[to]!=1 && d[u]!=Integer.MAX_VALUE &&((d[u]+dist)<d[to])){
                     d[to]=d[u]+dist;
                     parent[to]=u;
                 }

             }
             //color[u]=1;
             System.out.print(u+"=>");
         }



       return d;

    }
     public static int extractMin(int []d) {
         int min=Integer.MAX_VALUE;
         int idx=-1;
         for(int k=0;k<node;k++){
             if(color[k]!=1 && d[k]<=min){
                 min=d[k];
                 idx=k;
             }
         }
         color[idx]=1;
         return idx;

    }


}