Advertisement
Guest User

Untitled

a guest
Aug 24th, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.31 KB | None | 0 0
  1. //Dijkstra's Algo | https://informatics.mccme.ru/mod/statements/view3.php?id=193&chapterid=5#1
  2. //Made by @maximihajlov | PhTS2020a | 1-Jun-2019
  3.  
  4. import java.util.Scanner;
  5.  
  6. public class Dijkstra {
  7.     public static void main(String[] args) {
  8.         Scanner sc = new Scanner(System.in);
  9.  
  10.         int INF = Integer.MAX_VALUE / 2;
  11.  
  12.  
  13.         int N = sc.nextInt();
  14.         int S = sc.nextInt()-1;
  15.         int F = sc.nextInt()-1;
  16.  
  17.         int[][] m = new int[N][N];
  18.         for (int i = 0; i < N; i++)
  19.             for (int j = 0; j < N; j++) {
  20.                 m[i][j] = sc.nextInt();
  21.                 if(m[i][j]==-1)m[i][j]=INF;
  22.             }
  23.  
  24.         boolean[] used = new boolean[N];
  25.         int[] dist = new int[N];
  26.         for (int i = 0; i < N; i++) dist[i] = INF;
  27.         dist[S] = 0;
  28.  
  29.         while (true) {
  30.             int v = -1;
  31.             for (int i = 0; i < N; i++)
  32.                 if (!used[i] && dist[i] < INF && (v == -1 || dist[v] > dist[i]))
  33.                     v = i;
  34.             if (v == -1) break;
  35.             used[v] = true;
  36.             for (int i = 0; i < N; i++)
  37.                 if (!used[i] && m[v][i] < INF)
  38.                     dist[i] = Math.min(dist[i], dist[v] + m[v][i]);
  39.  
  40.         }
  41.         if(dist[F]<INF)System.out.println(dist[F]);
  42.         else System.out.println(-1);
  43.     }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement