#include using namespace std; class Graph { private: bool orient; int n, **arr, shet_reber, *d; public: Graph (int **matrix, int x, int shet) { n = x; arr = matrix; shet_reber = shet; d = new int[n]; } void minpath(int x); int get_length_path(int x, int y); }; void Graph::minpath(int x) { int w, min, j; bool *old = new bool[n]; int *path = new int[n]; for ( int i = 0; i < n; i++) { d[i] = arr[x][i]; old[i] = false; path[i] = x; } old[x] = true; for (int i = 1; i < n; i++) { for ( w = -1, min = INT8_MAX, j = 0; j < n; j++) if (!old[j] && d[j] < min) { w = j; min = d[j]; } if (w < 0) break; for (old[w] = true, j = 0; j < n; j++) if (!old[j] && d[j] > d[w] + arr[w][j]) { d[j] = d[w] + arr[w][j]; path[j] = w; } } delete [] old; } int Graph::get_length_path(int x, int y) { int dlina = 0; minpath(x); int i = y; if ( d[i] == INT8_MAX) dlina = -1; else dlina = d[i]; return dlina; } int main() { int n, shet_reber = 0, x, y; cin >> n >> x >> y; int **arr = new int*[n]; for ( int i = 0; i < n; i++) arr[i] = new int[n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> arr[i][j]; if (arr[i][j] != 0) shet_reber++; } Graph object(arr, n, shet_reber); cout << object.get_length_path(x-1, y-1); }