Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.Scanner;
- public class Dijkstra {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int inf = Integer.MAX_VALUE / 2;
- int n = in.nextInt();
- int s = in.nextInt();
- int f = in.nextInt();
- int[][] graph = new int[n][n];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- int cur = in.nextInt();
- if(cur == -1) {
- graph[i][j] = inf;
- } else {
- graph[i][j] = cur;
- }
- }
- }
- boolean[] mark = new boolean[n];
- int[] dist = new int[n];
- Arrays.fill(dist, inf);
- dist[s - 1] = 0;
- for (int i = 0; i < n; i++) {
- int cur = -1;
- int min = inf;
- for (int j = 0; j < n; j++) {
- if (!mark[j] && dist[j] <= min) {
- min = dist[j];
- cur = j;
- }
- }
- mark[cur] = true;
- for (int j = 0; j < n; j++) {
- dist[j] = Math.min(dist[j], dist[cur] + graph[cur][j]);
- }
- }
- if(dist[f - 1] == inf){
- System.out.println(-1);
- } else {
- System.out.println(dist[f - 1]);
- }
- in.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement