fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.   static int N, M, S, T;
  6.   static ArrayList<Integer>[] ady, pesos;
  7.   static int[] d, pi;
  8.   static boolean[] tachado; 
  9.   static int INFINITO = 1000000000;
  10.  
  11.   public static void main() {
  12.     leer_grafo();
  13.     dijkstra();
  14.     System.out.print(Arrays.toString(d));
  15.     System.out.print(Arrays.toString(pi));
  16.   }
  17.  
  18.   static void dijkstra() {
  19.     tachado = new boolean[N];
  20.     d = new int[N];
  21.     pi = new int[N];
  22.     Arrays.fill(d, INFINITO);
  23.     d[S] = 0;
  24.     Arrays.fill(pi, -1);
  25.     for(int i=0;i<N;i++) {
  26.       int U = siguiente_vertice();
  27.       tachado[U] = true;
  28.       for(int j=0; j<ady[U].size();j++) {
  29.         int V = ady[U].get(j);
  30.         int peso_V = pesos[U].get(j);
  31.         if (d[U] + peso_V < d[V]) {
  32.           d[V] = d[U] + peso_V;
  33.           pi[V] = U;
  34.         }
  35.       }
  36.     }
  37.   }
  38.  
  39.   static int siguiente_vertice() {
  40.     int sig = -1;
  41.     int min_d = INFINITO;
  42.     for(int i=0;i<N;i++) {
  43.       if (tachado[i]) continue; //Ignore los tachados
  44.       if (d[i] < min_d) {
  45.         min_d = d[i];
  46.         sig = i;
  47.       }
  48.     }
  49.     return sig;
  50.   }
  51.  
  52.   static void leer_grafo() {
  53.     Scanner lector = new Scanner(System.in);
  54.     N = lector.nextInt();    M = lector.nextInt();
  55.     S = lector.nextInt();    T = lector.nextInt();
  56.     ady = new ArrayList[N]; 
  57.     pesos = new ArrayList[N];
  58.     for(int i=0;i<N;i++) {
  59.       ady[i] = new ArrayList<Integer>();
  60.       pesos[i] = new ArrayList<Integer>();
  61.     }
  62.     for(int i=0;i<M;i++) {
  63.       int v1 = lector.nextInt();
  64.       int v2 = lector.nextInt();
  65.       int peso = lector.nextInt();
  66.       ady[v1].add(v2);
  67.       pesos[v1].add(peso);
  68.       ady[v2].add(v1);
  69.       pesos[v2].add(peso);
  70.     }
  71.   }
  72. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
7 11 0 6
0 1 10
0 2 4
0 3 5
1 4 20
1 2 5
2 3 8
2 5 10
2 4 30
3 5 5
4 6 30
5 6 12
compilation info 
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
spoj: The program compiled successfully, but main class was not found.
      Main class should contain method: public static void main (String[] args).
stdout
copy 
Standard output is empty
https://ideone.com/QkFimX
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!