Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Dijkstra's Algo | https://informatics.mccme.ru/mod/statements/view3.php?id=193&chapterid=5#1
- //Made by @maximihajlov | PhTS2020a | 1-Jun-2019
- import java.util.Scanner;
- public class Dijkstra {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int INF = Integer.MAX_VALUE / 2;
- int N = sc.nextInt();
- int S = sc.nextInt()-1;
- int F = sc.nextInt()-1;
- int[][] m = new int[N][N];
- for (int i = 0; i < N; i++)
- for (int j = 0; j < N; j++) {
- m[i][j] = sc.nextInt();
- if(m[i][j]==-1)m[i][j]=INF;
- }
- boolean[] used = new boolean[N];
- int[] dist = new int[N];
- for (int i = 0; i < N; i++) dist[i] = INF;
- dist[S] = 0;
- while (true) {
- int v = -1;
- for (int i = 0; i < N; i++)
- if (!used[i] && dist[i] < INF && (v == -1 || dist[v] > dist[i]))
- v = i;
- if (v == -1) break;
- used[v] = true;
- for (int i = 0; i < N; i++)
- if (!used[i] && m[v][i] < INF)
- dist[i] = Math.min(dist[i], dist[v] + m[v][i]);
- }
- if(dist[F]<INF)System.out.println(dist[F]);
- else System.out.println(-1);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement