Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package lab3;
- import java.io.*;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Random;
- import java.util.StringTokenizer;
- public class TaskB {
- FastScanner in;
- PrintWriter out;
- void solve() throws FileNotFoundException {
- int n = in.nextInt();
- int s = in.nextInt() - 1;
- int f = in.nextInt() - 1;
- long[][] edges = new long[n][n];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- edges[i][j] = in.nextLong();
- }
- }
- long[] d = new long[n];
- boolean[] marked = new boolean[n];
- Arrays.fill(d, -1);
- d[s] = 0;
- // System.out.println(Arrays.toString(d));
- for (int i = 0; i < n; i++) {
- Integer x = null;
- for (int j = 0; j < n; j++) {
- if (!marked[j] && (x == null || d[j] < d[x]) && d[j] != -1) {
- x = j;
- }
- }
- System.out.println(x);
- if (x == null || d[x] == -1) break;
- marked[x] = true;
- for (int j = 0; j < n; j++) {
- if (edges[x][j] != -1 && edges[x][j] != 0) {
- if (d[j] == -1 || d[x] + edges[x][j] < d[j]) {
- d[j] = d[x] + edges[x][j];
- }
- }
- }
- // System.out.println(Arrays.toString(d));
- }
- out.println(d[f]);
- }
- class Edge implements Comparable<Edge> {
- int weight;
- int a, b;
- Edge(int a, int b, int weight) {
- this.a = a - 1;
- this.b = b - 1;
- this.weight = weight;
- }
- @Override
- public int compareTo(Edge o) {
- return Integer.compare(weight, o.weight);
- }
- }
- public void run() {
- try {
- in = new FastScanner(new File("pathmgep.in"));
- out = new PrintWriter(new File("pathmgep.out"));
- solve();
- out.close();
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- public static void main(String[] args) throws FileNotFoundException {
- new TaskB().run();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- String str;
- FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- try {
- if ((str = br.readLine()) == null) return null;
- st = new StringTokenizer(str);
- } catch (Exception e) {
- e.printStackTrace();
- return null;
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement