Advertisement
Hydron

Путь в графе

Dec 7th, 2021
1,041
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. /// https://informatics.msk.ru/mod/statements/view3.php?chapterid=160#1
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7.     int n;
  8.     cin >> n;
  9.     int graph[n+1][n+1];
  10.     vector < int > g[n+1];
  11.     for (int i=1; i<=n; i++){
  12.         for (int j=1; j<=n; j++){
  13.             cin >> graph[i][j];
  14.             if (graph[i][j] == 1){
  15.                 g[i].push_back(j);
  16.                 //g[j].push_back(i);
  17.             }
  18.         }
  19.     }
  20.     int s, f;
  21.     cin >> s >> f;
  22.     int used[n+1], dist[n+1], from[n+1]; // used[i] = 1, якщо <i> Була відвідана
  23.     for (int i=0; i<=n; i++) used[i] = 0, from[i] = 0;
  24.     vector < int > q;
  25.     q.push_back(s);
  26.     used[s] = 1;
  27.     dist[s] = 0;
  28.     int point = 0;
  29.     while(point < q.size()){
  30.         int v = q[point];
  31.         for (int i=0; i<g[v].size(); i++){
  32.             int to = g[v][i];
  33.             if (used[to] == 0){
  34.                 used[to] = 1;
  35.                 from[to] = v;
  36.                 dist[to] = dist[v] + 1;
  37.                 q.push_back(to);
  38.             }
  39.         }
  40.         point ++;
  41.     }
  42.     if (used[f] == 1){
  43.         cout << dist[f] << endl;
  44.         if (dist[f] > 0){
  45.             vector < int > ans;
  46.             while(f != 0){
  47.                 ans.push_back(f);
  48.                 //cout << f << ' ';
  49.                 f = from[f];
  50.             }
  51.             for (int i=ans.size()-1; i>-1; i--) cout << ans[i] << ' ';
  52.         }
  53.     }else cout << -1;
  54.     return 0;
  55. }
  56. /*
  57. Breadth First Search
  58. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement