fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         Scanner input = new Scanner(System.in);
  8.  
  9.         int v = input.nextInt();
  10.         int dist[] = new int[v + 1];
  11.         Arrays.fill(dist, Integer.MAX_VALUE);
  12.         int e = input.nextInt();
  13.         ArrayList<int []> lists[] = new ArrayList[v + 1];
  14.         for(int i = 1; i <=v; i++)
  15.             lists[i] = new ArrayList<>();
  16.  
  17.         Queue<int[]> que = new PriorityQueue<>((a, b) -> {
  18.             if (a[1] < b[1]) return -1;
  19.             else if (a[1] > b[1]) return 1;
  20.             else return 0;
  21.         });
  22.  
  23.         int start = input.nextInt();
  24.         dist[start] = 0;
  25.  
  26.         for (int i = 0; i < e; i++) {
  27.             int a = input.nextInt();
  28.             int b = input.nextInt();
  29.             int c = input.nextInt();
  30.  
  31.             int temp[] = new int[2];
  32.             temp[0] = b;
  33.             temp[1] = c;
  34.  
  35.             lists[a].add(temp);
  36.  
  37.             if (a == start) {
  38.                 dist[b] = c;
  39.                 que.add(temp);
  40.             }
  41.  
  42.         }
  43.  
  44.         while (!que.isEmpty()) {
  45.  
  46.             int temp[] = que.poll();
  47.             int current = temp[0];
  48.             int value = temp[1];
  49.  
  50.             for(int i = 0; i < lists[current].size(); i++){
  51.                 int next[] = new int[2];
  52.                 next[0] = lists[current].get(i)[0];
  53.                 next[1] = value + lists[current].get(i)[1];
  54.                 if(dist[next[0]] > next[1]){
  55.                     dist[next[0]] = next[1];
  56.                     que.add(next);
  57.                 }
  58.             }
  59.  
  60.         }
  61.  
  62.         for (int i = 1; i <= v; i++)
  63.             if (dist[i] != Integer.MAX_VALUE) System.out.println(dist[i]);
  64.             else System.out.println("INF");
  65.  
  66.  
  67.     }
  68.  
  69. }
  70.  
Success #stdin #stdout 0.15s 2184192KB
comments (?)
stdin
copy 
2 2
1
1 2 1
1 2 2
stdout
copy 
0
2
https://ideone.com/kFPKzG
language:
Java (HotSpot 12)
created:
5 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!