Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.05 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.Scanner;
  3.  
  4. public class Dijkstra {
  5.  
  6. public static void main(String[] args) {
  7.  
  8. Scanner in = new Scanner(System.in);
  9. int inf = Integer.MAX_VALUE / 2;
  10. int n = in.nextInt();
  11.  
  12. int s = in.nextInt();
  13. int f = in.nextInt();
  14. int[][] graph = new int[n][n];
  15. for (int i = 0; i < n; i++) {
  16. for (int j = 0; j < n; j++) {
  17. int cur = in.nextInt();
  18. if(cur == -1) {
  19. graph[i][j] = inf;
  20. } else {
  21. graph[i][j] = cur;
  22. }
  23. }
  24. }
  25. boolean[] mark = new boolean[n];
  26. int[] dist = new int[n];
  27. Arrays.fill(dist, inf);
  28. dist[s - 1] = 0;
  29. for (int i = 0; i < n; i++) {
  30. int cur = -1;
  31. int min = inf;
  32. for (int j = 0; j < n; j++) {
  33. if (!mark[j] && dist[j] <= min) {
  34. min = dist[j];
  35. cur = j;
  36. }
  37. }
  38. mark[cur] = true;
  39. for (int j = 0; j < n; j++) {
  40. dist[j] = Math.min(dist[j], dist[cur] + graph[cur][j]);
  41. }
  42. }
  43. if(dist[f - 1] == inf){
  44. System.out.println(-1);
  45. } else {
  46. System.out.println(dist[f - 1]);
  47. }
  48. in.close();
  49. }
  50.  
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement