irapilguy

Untitled

Nov 26th, 2017
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5. #define N 101
  6. vector <int> mas[N];
  7. int res[N];
  8. int used[N];
  9. int n;
  10. void bfs(int start, int finish) {
  11.     queue <int> q;
  12.     q.push(start);
  13.     used[start] = 1;
  14.     while (q.size() != 0) {
  15.         start = q.front();
  16.         q.pop();
  17.         for (int i = 0; i < n; i++) {
  18.             if (used[i] == 0 && mas[start][i] != -1) {
  19.                 q.push(i);
  20.                 used[i] = 1;
  21.             }
  22.             int per = res[start] + mas[start][i];
  23.             if (res[i] != 0 && mas[start][i] != -1 && res[i] > per) {
  24.                 res[i] = per;
  25.                 q.push(i);
  26.             }
  27.         }
  28.     }
  29. }
  30. int main() {
  31.     int start, finish;
  32.     cin >> n >> start >> finish;
  33.     for (int i = 0; i < n; i++) {
  34.         for (int j = 0; j < n; j++) {
  35.             int x;
  36.             cin >> x;
  37.             mas[i].push_back(x);
  38.         }
  39.     }
  40.     for (int i = 0; i < n; i++) res[i] = 1000000;
  41.     res[start - 1] = 0;
  42.     bfs(start - 1, finish - 1);
  43.     int way = res[finish - 1];
  44.     if (way != 1000000) cout << way;
  45.     else cout << "-1";
  46.     return 0;
  47. }
Add Comment
Please, Sign In to add comment